Lightoj 1070 - Algebraic Problem

problem_link

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define llu long long unsigned
4. llu c[2][2];
5. //llu MOD=11221212121121;
6. llu p, q,n;
7. void mul(llu a[2][2],llu b[2][2]){
8.     memset(c, 0, sizeof(c));
9.     for(int i = 0; i <2; i++){
10.         for(int j = 0; j <2; j++){
11.             for(int k = 0; k <2; k++){
12.                 c[i][j]+= ((a[i][k])*(b[k][j]));
13.                 //c[j][j]%=MOD;
14.             }
15.         }
16.     }
17.     for(int i = 0; i <2; i++){
18.         for(int j = 0; j <2; j++){
19.             a[i][j] = c[i][j];
20.         }
21.     }
22. }
23. void ans(llu a[2][2], llu n){
24.     llu m[2][2] = {{p, -q}, {1,0}};
25.     if(n == 1) return;
26.     ans(a, n/2);
27.     mul(a, a);
28.     if(n%2) mul(a, m);
29. }
30. int main(){
31.     int ts;
32.     scanf("%d", &ts);
33.     for(int s = 1; s <= ts; s++){
34.     llu answer;
35.     scanf("%llu%llu%llu",&p, &q, &n);
36.     llu f[2][2] = {{p, -q}, {1,0}};
37.     //llu f1 = p%MOD;
38.     //llu f2 = ((p%MOD)*(p%MOD))%MOD-(2*q)%MOD;
39.     if(n<1) answer = 2;
40.     else if(n == 1) answer = p;
41.     //else if(n == 2) answer  = f2;
42.     else if(n>1) ans(f, n-1), answer = (p*f[0][0]+2*f[0][1]);
43.     printf("Case %d: %llu\n", s,answer);
44.     }
45.     return 0;
46. }

for any queries just comment :)