maksyuki 发表于 oj 分类,标签:

1070 - Algebraic Problem

InputGiven the value of a+b and ab you will have to find the value of an+bna and b not necessarily have to be real numbers.

Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case contains three non-negative integers, p, q and n. Here p denotes the value of a+b and q denotes the value of ab. Each number in the input file fits in a signed 32-bit integer. There will be no such input so that you have to find the value of 00.


For each test case, print the case number and (an+bn) modulo 264.

Sample Input

Output for Sample Input

210 16 27 12 3 Case 1: 68Case 2: 91



算法分析:首先推出递推公式:Sn = p*Sn-1 - q * Sn-2,然后使用矩阵快速幂取模求解。注意要使用unsigned long long 来定义变量,输入、输出!!!!!!