fork download 
  1. #include<bits/stdc++.h>
  2. #define file "remainder"
  3.  
  4. using namespace std;
  5.  
  6. #define int long long
  7. #define pii pair<int,int>
  8. #define vi vector<int>
  9. #define pb push_back
  10. #define mp make_pair
  11. #define X first
  12. #define Y second
  13. #define vii vector<vector<int>>
  14.  
  15. const int N=1e6+5;
  16. const int NN=1e3+9;
  17. const int MOD=1e9+7;
  18. const int INF=1e18;
  19.  
  20. int x, n, m;
  21. vii dp(3, vector<int> (3, 0));
  22.  
  23. int nhan(int a, int b) {
  24.     if (b==0) return 0;
  25.     if (b==1) return a;
  26.     int tmp=nhan(a,b/2)%m;
  27.     if (b&1)
  28.         return (((tmp+tmp)%m)+a)%m;
  29.     return (tmp+tmp)%m;
  30. }
  31.  
  32. vii mul(const vii& a, const vii& b) {
  33.     vii res(3, vector<int> (3, 0));
  34.     for (int i=1;i<=2;i++)
  35.     for (int j=1;j<=2;j++)
  36.     for (int k=1;k<=2;k++) {
  37.         res[i][j]+=(nhan(a[i][k],b[k][j]))%m;
  38.         res[i][j]%=m;
  39.     }
  40.     return res;
  41. }
  42.  
  43. void inkq(const vii& a) {
  44.     for (int i=1;i<=2;i++) {
  45.         for (int j=1;j<=2;j++)
  46.             cout<<a[i][j]<<" ";
  47.         cout<<endl;
  48.     }
  49. }
  50.  
  51. vii pow(const vii& a, int b) {
  52.     if (b==1) return a;
  53.     vii tmp=pow(a,b/2);
  54.     if (b&1)
  55.         return mul(mul(tmp,tmp),a);
  56.     return mul(tmp,tmp);
  57. }
  58.  
  59. int cc(int x) {
  60.     int res=1;
  61.     int dem=0;
  62.     while (x>0) {
  63.         dem++;
  64.         x/=10;
  65.     }
  66.     for (int i=1;i<=dem;i++) {
  67.         res*=10;
  68.         res%=m;
  69.     }
  70.     return res;
  71. }
  72.  
  73. void process() {
  74.     cin>>x>>n>>m;
  75.     vii t(3, vector<int> (3, 0));
  76.     t[1][1]=cc(x);
  77.     t[1][2]=x%m;
  78.     t[2][1]=0;
  79.     t[2][2]=1;
  80.     dp=pow(t,n);
  81. //    inkq(dp);
  82.     cout<<dp[1][2];
  83. }
  84.  
  85. signed main() {
  86.     cin.tie(0)->sync_with_stdio(0);
  87.     // freopen(file".inp","r",stdin);
  88.     // freopen(file".out","w",stdout);
  89.     int t=1;
  90. //    cin>>t;
  91.     while (t--)
  92.         process();
  93.     return 0;
  94. }
  95.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
24680 1357913579 777777777
stdout 
484072840
https://ideone.com/BWzClK
language:
C++14 (gcc 8.3)
created:
3 days 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!