fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. void carry(vector<int>&a)
  6. {
  7.     int i;
  8.     for(i=0;i<a.size();i++)
  9.     {
  10.         if(a[i]>=10)
  11.         {
  12.             if(i+1<a.size())
  13.                 a[i+1]+=a[i]/10;
  14.             else
  15.                 a.push_back(a[i]/10);
  16.             a[i]%=10;
  17.         }
  18.     }
  19.     return;
  20. }
  21.  
  22. vector<int> add(vector<int>a,vector<int>b)
  23. {
  24.     int i;
  25.     vector<int>c;
  26.     for(i=0;i<a.size();i++)
  27.         c.push_back(a[i]);
  28.  
  29.     for(i=0;i<b.size();i++)
  30.     {
  31.         if(i<c.size())
  32.             c[i]+=b[i];
  33.         else
  34.             c.push_back(b[i]);
  35.     }
  36.     carry(c);
  37.     return c;
  38. }
  39.  
  40. vector<int> mul(vector<int>a,int b)
  41. {
  42.     int i;
  43.     vector<int>c;
  44.     for(i=0;i<a.size();i++)
  45.     {
  46.         c.push_back(a[i]*b);
  47.     }
  48.     carry(c);
  49.     return c;
  50. }
  51.  
  52. vector<int> div(vector<int>a,int b)
  53. {
  54.     int i;
  55.     int tmp=0;
  56.     vector<int>c;
  57.     i=a.size()-1;
  58.     if(a[i]<b)
  59.     {
  60.         tmp=a[i];
  61.         i--;
  62.     }
  63.     for(;i>=0;i--)
  64.     {
  65.         tmp*=10;
  66.         tmp+=a[i];
  67.         c.push_back(tmp/b);
  68.         tmp%=b;
  69.     }
  70.     reverse(c.begin(),c.end());
  71.     return c;
  72. }
  73.  
  74. void display(vector<int>a)
  75. {
  76.     int i;
  77.     for(i=a.size()-1;i>=0;i--)
  78.     {
  79.         printf("%d",a[i]);
  80.     }
  81.     printf("\n");
  82.     return;
  83. }
  84. //[M mod 5][2^k mod 5]
  85. const int table[5][5]={{0,5,5,5,5},
  86.                        {0,9,7,3,1},
  87.                        {0,3,9,1,7},
  88.                        {0,7,1,9,3},
  89.                        {0,1,3,7,9}};
  90.  
  91. int main()
  92. {
  93.     int i,j;
  94.  
  95.     vector<int>M(1,0);
  96.     vector<int>two(1,1);
  97.     vector<int>ans;
  98.     int n;
  99.     scanf("%d",&n);
  100.     for(i=0;i<n;i++)
  101.     {
  102. //        printf("calculating on %dth...\n",i);
  103.         int X=table[ M[0]%5 ][ two[0]%5 ];
  104.         M = div( add( mul( two, X), M) , 5);
  105.         two=mul(two,2);
  106. //        printf("%d\n",X);
  107.         ans.push_back(X);
  108. //        display(M);
  109. //        display(two);
  110. //        system("PAUSE");
  111.     }
  112. //    printf("ans=");
  113.     display(ans);
  114.  
  115.     return 0;
  116. }
  117.  
Time limit exceeded #stdin #stdout 5s 15912KB
comments (?)
stdin
copy 
55555
stdout
copy 
Standard output is empty
https://ideone.com/tsgzNx
language:
C++14 (clang 8.0)
created:
5 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!