1070 - Algebraic Problem
InputGiven the value of a+b and ab you will have to find the value of an+bn. a 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.
Output
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 来定义变量，输入、输出！！！！！！
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; const int INF = 0x7FFFFFFF; const unsigned long long MOD = 18446744073709551615uLL; //18446744073709551615 const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 2; unsigned long long n = 2;//表示方阵的尺寸，必须恰好为运算的大小 //申请变量 struct Mat { unsigned long long mat[maxn][maxn]; }; //重载Mat乘法运算 Mat operator * (Mat a, Mat b) { Mat c; memset (c.mat, 0, sizeof (c.mat)); for (unsigned long long k = 0; k < n; k++) { for (unsigned long long i = 0; i < n; i++) { if (a.mat[i][k] == 0) continue; for (unsigned long long j = 0; j < n; j++) { if (b.mat[k][j] == 0) continue; //c.mat[i][j] = (c.mat[i][j] + ((a.mat[i][k] % MOD) * (b.mat[k][j] % MOD) % MOD)) % MOD; c.mat[i][j] = (c.mat[i][j] + (a.mat[i][k] * b.mat[k][j]) % MOD) % MOD; } } } return c; } //重载Mat乘幂运算 Mat operator ^ (Mat a, unsigned long long k) { Mat c; for (unsigned long long i = 0; i < n; i++) for(unsigned long long j = 0; j < n; j++) c.mat[i][j] = (i == j); while (k) { if(k & 1) c = c * a; a = a * a; k >>= 1; } return c; } int main() { // ifstream cin ("aaa.txt"); // freopen ("aaa.txt", "r", stdin); Mat aa; int t, flag =1; scanf ("%d", &t); while (t--) { unsigned long long p, q, n; scanf ("%llu%llu%llu", &p, &q, &n); printf ("Case %d: ", flag++); if (n == 0) puts ("2"); else if (n == 1) printf ("%llu\n", p % MOD); //cout << p % MOD << endl; else if (n == 2) printf ("%llu\n", (p * p - 2 * q) % MOD); //cout << (p * p - 2 * q) % MOD << endl; else { aa.mat[0][0] = p, aa.mat[0][1] = -q; aa.mat[1][0] = 1, aa.mat[1][1] = 0; Mat bb = aa ^ (n - 2), cc; // cout << aa.mat[0][0] << " " << aa.mat[0][1] << endl; // cout << aa.mat[1][0] << " " << aa.mat[1][1] << endl; cc.mat[0][0] = (p * p - 2 * q) % MOD; cc.mat[1][0] = p % MOD; bb = bb * cc; //printf ("%ulld\n", (bb.mat[0][0] + MOD) % MOD); if (bb.mat[0][0] > 0) printf ("%llu\n", bb.mat[0][0] % MOD); //cout << bb.mat[0][0] % MOD << endl; else printf ("%llu\n", (bb.mat[0][0] + MOD) %MOD); //cout << (bb.mat[0][0] + MOD) % MOD + 1<< endl; } } return 0; } |
- « 上一篇：lightoj1067
- lightoj1074：下一篇 »