fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. using cd = complex<double>;
  6. const double PI = acos(-1);
  7.  
  8. void fft(vector<cd> & a, bool invert) {
  9.     int n = a.size();
  10.     if (n == 1)
  11.         return;
  12.  
  13.     vector<cd> a0(n / 2), a1(n / 2);
  14.     for (int i = 0; 2 * i < n; i++) {
  15.         a0[i] = a[2*i];
  16.         a1[i] = a[2*i+1];
  17.     }
  18.     fft(a0, invert);
  19.     fft(a1, invert);
  20.  
  21.     double ang = 2 * PI / n * (invert ? -1 : 1);
  22.     cd w(1), wn(cos(ang), sin(ang));
  23.     for (int i = 0; 2 * i < n; i++) {
  24.         a[i] = a0[i] + w * a1[i];
  25.         a[i + n/2] = a0[i] - w * a1[i];
  26.         if (invert) {
  27.             a[i] /= 2;
  28.             a[i + n/2] /= 2;
  29.         }
  30.         w *= wn;
  31.     }
  32. }
  33.  
  34. vector<int> multiply(vector<int> const& a, vector<int> const& b) {
  35.     vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
  36.     int n = 1;
  37.     while (n < a.size() + b.size()) 
  38.         n <<= 1;
  39.     fa.resize(n);
  40.     fb.resize(n);
  41.  
  42.     fft(fa, false);
  43.     fft(fb, false);
  44.     for (int i = 0; i < n; i++)
  45.         fa[i] *= fb[i];
  46.     fft(fa, true);
  47.  
  48.     vector<int> result(n);
  49.     for (int i = 0; i < n; i++)
  50.         result[i] = round(fa[i].real());
  51.  
  52.     int carry = 0;
  53.     for (int i = 0; i < n; i++){
  54.         result[i] += carry;
  55.         carry = result[i] / 10;
  56.         result[i] %= 10;
  57.     }
  58.     return result;
  59. }
  60.  
  61. vector<int> subtractStrings(vector<int> &a, vector<int> &b) {
  62.     vector<int> result;
  63.     int borrow = 0;
  64.     int i = (int)a.size() - 1;
  65.     int j = (int)b.size() - 1;
  66.     while (i >= 0) {
  67.         int diff = a[i--] - borrow;
  68.         if (j >= 0) diff -= b[j--];
  69.         if (diff < 0) {
  70.             diff += 10;
  71.             borrow = 1;
  72.         } else {
  73.             borrow = 0;
  74.         }
  75.         result.push_back(diff);
  76.     }
  77.     // Remove leading zeros from the result
  78.     while (result.size() > 1 && result.back() == '0') {
  79.         result.pop_back();
  80.     }
  81.     reverse(result.begin(), result.end());
  82.     return result;
  83. }
  84.  
  85. int main() {
  86.     if(strcmp(__FILE__,"tempCodeRunnerFile.cpp")==0) freopen("input.txt","r",stdin);
  87.     int tc=1;
  88.     scanf("%d",&tc);
  89.     while(tc--){
  90.         int x, n;
  91.         scanf("%d %d",&x,&n);
  92.         int denominator = x - 1;
  93.         vector<int> numerator={1},one={1},X;
  94.         while(x){
  95.             X.push_back(x%10);
  96.             x/=10;
  97.         }        
  98.         while(X.size()<1024) X.push_back(0);
  99.         while(numerator.size()<1024) numerator.push_back(0);
  100.         // binary exponentiation
  101.         while(n){
  102.             if(n&1) numerator=multiply(X,numerator);
  103.             X=multiply(X,X);
  104.             n/=2;
  105.         }
  106.         // removing leading zeroes
  107.         while(!numerator.empty()){
  108.             if(numerator.back()==0) numerator.pop_back();
  109.             else break;
  110.         }
  111.         reverse(numerator.begin(),numerator.end());
  112.  
  113.         numerator=subtractStrings(numerator,one);
  114.         for(int val:numerator){
  115.             printf("%d",val);
  116.         }
  117.         printf("/%d\n",denominator);
  118.     }
  119.     return 0;
  120. }
  121.  
Success #stdin #stdout 0.03s 5276KB
comments (?)
stdin
copy 
1
5 10
stdout
copy 
9765624/4
https://ideone.com/VGp1h4
language:
C++14 (gcc 8.3)
created:
4 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!