fork(2) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. ll mm,mod;
  5. struct matran{
  6.     ll a[2][2];
  7.     void print(){
  8.             for(ll i=0;i<2;i++){
  9.                     for(ll j=0;j<2;j++) cout<<a[i][j]<<" ";
  10.                     cout<<'\n';
  11.             }
  12.     }
  13. };
  14. matran mot;
  15. struct cap{
  16.    ll u,u_plus_1;
  17.    void print(){
  18.            cout<<u<<" "<<u_plus_1<<'\n';
  19.    }
  20. };
  21. ll f(ll a,ll n, ll MOD){
  22.         ll res=a,ans=0;
  23.         while(n){
  24.                 if(n%2) ans = (ans+res)%MOD;
  25.                 res=(res+res)%MOD;
  26.                 n/=2;
  27.         }
  28.         return ans;
  29. }
  30. ll po1(ll a,ll n, ll MOD){
  31.         ll res=a,ans=1;
  32.         while(n){
  33.                 if(n%2) ans=ans*res%MOD;
  34.                 res=res*res%MOD;
  35.                 n/=2;
  36.         }
  37.         return ans;
  38. }
  39. matran prod(matran A,matran B){
  40.         matran anss;
  41.         anss.a[0][0]=(f(A.a[0][0],B.a[0][0],mod) + f(A.a[0][1],B.a[1][0],mod))%mod;
  42.         anss.a[0][1]=(f(A.a[0][0],B.a[0][1],mod) + f(A.a[0][1],B.a[1][1],mod))%mod;
  43.         anss.a[1][0]=(f(A.a[1][0],B.a[0][0],mod) + f(A.a[1][1],B.a[1][0],mod))%mod;
  44.         anss.a[1][1]=(f(A.a[1][0],B.a[0][1],mod) + f(A.a[1][1],B.a[1][1],mod))%mod;
  45.         return anss;
  46. }
  47. matran po(matran X,ll n){
  48.         matran res = X, ans = mot;
  49.         while(n){
  50.                 if(n%2) ans = prod(ans,res);
  51.                 res = prod(res,res);
  52.                 n/=2;
  53.         }
  54.         return ans;
  55. }
  56. cap prod1(cap pp, matran X){
  57.         cap ans;
  58.         ans.u = (f(pp.u,X.a[0][0],mod)+f(pp.u_plus_1,X.a[1][0],mod))%mod;
  59.         ans.u_plus_1 =  (f(pp.u,X.a[1][0],mod)+f(pp.u_plus_1,X.a[1][1],mod))%mod;
  60.         return ans;
  61. }
  62. int main(){
  63.         // freopen("lala.inp","r",stdin);
  64.         // freopen("lala.out","w",stdout);
  65.  
  66.         ll a,b,nn,xx,testcase;
  67.         // cin>>testcase;
  68.         testcase = 1;
  69.         for(ll qq=1;qq<=testcase;qq++){
  70.         //  cin>>a>>b;
  71.         cin>>xx>>nn>>mm;
  72.         mod = mm;
  73.         ll p,q,len;
  74.         len = to_string(xx).size();
  75.         p=po1(10,len,mm);
  76.         q=xx%mm;
  77.         cap init;
  78.         init.u = q;
  79.         init.u_plus_1 = 1;
  80.         matran M;
  81.         M.a[0][0]=p;
  82.         M.a[0][1]=0;
  83.         M.a[1][0]=q;
  84.         M.a[1][1]=1;
  85.         mot.a[0][0]=1;
  86.         mot.a[0][1]=0;
  87.         mot.a[1][0]=0;
  88.         mot.a[1][1]=1;
  89.  
  90.         matran res = po(M,nn-1);
  91.         cap ansss = prod1(init,res);
  92.         cout<<ansss.u<<'\n';
  93.  
  94.         }
  95.  
  96. }
Success #stdin #stdout 0s 4892KB
comments (?)
stdin
copy 
5 2 27
stdout
copy 
1
https://ideone.com/JgahaD
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!