- #include <bits/stdc++.h>
- using namespace std;
- #define llu long long unsigned
- llu c[2][2];
- //llu MOD=11221212121121;
- llu p, q,n;
- void mul(llu a[2][2],llu b[2][2]){
- memset(c, 0, sizeof(c));
- for(int i = 0; i <2; i++){
- for(int j = 0; j <2; j++){
- for(int k = 0; k <2; k++){
- c[i][j]+= ((a[i][k])*(b[k][j]));
- //c[j][j]%=MOD;
- }
- }
- }
- for(int i = 0; i <2; i++){
- for(int j = 0; j <2; j++){
- a[i][j] = c[i][j];
- }
- }
- }
- void ans(llu a[2][2], llu n){
- llu m[2][2] = {{p, -q}, {1,0}};
- if(n == 1) return;
- ans(a, n/2);
- mul(a, a);
- if(n%2) mul(a, m);
- }
- int main(){
- int ts;
- scanf("%d", &ts);
- for(int s = 1; s <= ts; s++){
- llu answer;
- scanf("%llu%llu%llu",&p, &q, &n);
- llu f[2][2] = {{p, -q}, {1,0}};
- //llu f1 = p%MOD;
- //llu f2 = ((p%MOD)*(p%MOD))%MOD-(2*q)%MOD;
- if(n<1) answer = 2;
- else if(n == 1) answer = p;
- //else if(n == 2) answer = f2;
- else if(n>1) ans(f, n-1), answer = (p*f[0][0]+2*f[0][1]);
- printf("Case %d: %llu\n", s,answer);
- }
- return 0;
- }
for any queries just comment :)
No comments:
Post a Comment