Saturday 29 July 2017

Lightoj 1070 - Algebraic Problem

  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, 0sizeof(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(== 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(== 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. }

No comments:

Post a Comment

Most Featured Post

Lightoj 1159 - Batman

http://lightoj.com/volume_showproblem.php?problem=1159 problem analysis: First i thought of this as if s1, s2 and s3 are those three str...