ccbeginner

UVa Q10518

Feb 29th, 2020
108
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /******************************************************************************
  2.  
  3.                               Online C++ Compiler.
  4.                Code, Compile, Run and Debug C++ program online.
  5. Write your code in this editor and press "Run" button to compile and execute it.
  6.  
  7. *******************************************************************************/
  8.  
  9. #include <bits/stdc++.h>
  10. using namespace std;
  11. #define int long long
  12.  
  13. int n,m;
  14. int cur[3][3], uni[3][3] = {{0,1,0},{1,1,0},{0,1,1}};
  15. int ori[3] = {-1,1,1};
  16.  
  17. void self(){
  18.     int des[3][3];
  19.     for(int i = 0; i < 3; ++i){
  20.         for(int j = 0; j < 3; ++j){
  21.             des[i][j] = 0;
  22.             for(int k = 0; k < 3; ++k)des[i][j] += cur[i][k] * cur[k][j];
  23.             des[i][j] %= m;
  24.         }
  25.     }
  26.     memcpy(cur, des, sizeof(des));
  27. }
  28.  
  29. void mode(){
  30.     int des[3][3];
  31.     for(int i = 0; i < 3; ++i){
  32.         for(int j = 0; j < 3; ++j){
  33.             des[i][j] = 0;
  34.             for(int k = 0; k < 3; ++k)des[i][j] += cur[i][k] * uni[k][j];
  35.             des[i][j] %= m;
  36.         }
  37.     }
  38.     memcpy(cur, des, sizeof(des));
  39. }
  40.  
  41. void mi(int val){
  42.     if(val == 0 || val == 1){
  43.         memcpy(cur, uni, sizeof(uni));
  44.     }else if(val % 2 == 0){
  45.         mi(val/2);
  46.         self();
  47.     }else{
  48.         mi(val/2);
  49.         self();
  50.         mode();
  51.     }
  52. }
  53.  
  54. int32_t main(){
  55.     int cnt = 0;
  56.     while(cin >> n >> m){
  57.         if(n == 0 && m == 0)break;
  58.         mi(n);
  59.         int ans[3] = {0};
  60.         for(int i = 0; i < 3; ++i){
  61.             for(int j = 0; j < 3; ++j){
  62.                 ans[i] += ori[j] * cur[j][i];
  63.                 ans[i] %= m;
  64.             }
  65.         }
  66.         cout << "Case " << ++cnt << ": " << n << ' ' << m << ' ' << (ans[1]+m)%m << '\n';
  67.     }
  68.     return 0;
  69. }
RAW Paste Data