当前位置:   article > 正文

数学(论)里的一些定理(莫比乌斯反演,傅立叶变换,数论变换...)

莫比乌斯反演 傅里叶变换

莫比乌斯反演

莫比乌斯反演在数论中占有重要的地位,许多情况下能大大简化运算。那么我们先来认识莫比乌斯反演公式。

 

定理:是定义在非负整数集合上的两个函数,并且满足条件,那么我们得到结论

 

     

 

在上面的公式中有一个函数,它的定义如下:

 

    (1)若,那么

    (2)若均为互异素数,那么

    (3)其它情况下

 

 

对于函数,它有如下的常见性质:

 

    (1)对任意正整数

  

                            

 

        (2)对任意正整数

 

         

 

线性筛选求莫比乌斯反演函数代码。

  1. void Init()
  2. {
  3. memset(vis,0,sizeof(vis));
  4. mu[1] = 1;
  5. cnt = 0;
  6. for(int i=2; i<N; i++)
  7. {
  8. if(!vis[i])
  9. {
  10. prime[cnt++] = i;
  11. mu[i] = -1;
  12. }
  13. for(int j=0; j<cnt&&i*prime[j]<N; j++)
  14. {
  15. vis[i*prime[j]] = 1;
  16. if(i%prime[j]) mu[i*prime[j]] = -mu[i];
  17. else
  18. {
  19. mu[i*prime[j]] = 0;
  20. break;
  21. }
  22. }
  23. }
  24. }

有了上面的知识,现在我们来证明莫比乌斯反演定理。

证明

证明完毕!

嗯,有了莫比乌斯反演,很多问题都可以简化了,接下来我们来看看莫比乌斯反演在数论中如何简化运算的。

题目:http://bz.cdqzoi.com/JudgeOnline/problem.php?id=2818

题意:给一个正整数,其中,求使得为质数的的个数,

分析:对于本题,因为是使得为质数,所以必然要枚举小于等于的质数,那么对于每一个质数,只

     需要求在区间中,满足有序对互质的对数。

     也就是说,现在问题转化为:在区间中,存在多少个有序对使得互质,这个问题就简单啦,因为

     是有序对,不妨设,那么我们如果枚举每一个,小于有多少个互素,这正是欧拉函数。所以

     我们可以递推法求欧拉函数,将得到的答案乘以2即可,但是这里乘以2后还有漏计算了的,那么有哪些呢?

     是且为素数的情况,再加上就行了。

代码:

  1. #include <iostream>
  2. #include <string.h>
  3. #include <stdio.h>
  4. #include <bitset>
  5. using namespace std;
  6. typedef long long LL;
  7. const int N = 10000010;
  8. bitset<N> prime;
  9. LL phi[N];
  10. LL f[N];
  11. int p[N];
  12. int k;
  13. void isprime()
  14. {
  15. k = 0;
  16. prime.set();
  17. for(int i=2; i<N; i++)
  18. {
  19. if(prime[i])
  20. {
  21. p[k++] = i;
  22. for(int j=i+i; j<N; j+=i)
  23. prime[j] = false;
  24. }
  25. }
  26. }
  27. void Init()
  28. {
  29. for(int i=1; i<N; i++) phi[i] = i;
  30. for(int i=2; i<N; i+=2) phi[i] >>= 1;
  31. for(int i=3; i<N; i+=2)
  32. {
  33. if(phi[i] == i)
  34. {
  35. for(int j=i; j<N; j+=i)
  36. phi[j] = phi[j] - phi[j] / i;
  37. }
  38. }
  39. f[1] = 0;
  40. for(int i=2;i<N;i++)
  41. f[i] = f[i-1] + (phi[i]<<1);
  42. }
  43. LL Solve(int n)
  44. {
  45. LL ans = 0;
  46. for(int i=0; i<k&&p[i]<=n; i++)
  47. ans += 1 + f[n/p[i]];
  48. return ans;
  49. }
  50. int main()
  51. {
  52. Init();
  53. isprime();
  54. int n;
  55. scanf("%d",&n);
  56. printf("%I64d\n",Solve(n));
  57. return 0;
  58. }

上题不算太难,普通的欧拉函数就可以搞定,接下来我们来看看它的升级版。


题意:给定两个数,其中,求为质数的有多少对?其中的范

     围是

 

分析:本题与上题不同的是不一定相同。在这里我们用莫比乌斯反演来解决,文章开头也说了它能大大简化

     运算。我们知道莫比乌斯反演的一般描述为:

 

     

 

     其实它还有另一种描述,本题也是用到这种。那就是:

 

     

 

     好了,到了这里,我们开始进入正题。。。

 

     对于本题,我们设

 

     为满足的对数

     为满足的对数

 

     那么,很显然,反演后得到

 

     因为题目要求是为质数,那么我们枚举每一个质数,然后得到

 

     

 

     如果直接这样做肯定TLE,那么我们必须优化。

 

     我们设,那么继续得到

 

     到了这里,可以看出如果我们可以先预处理出所有的对应的的值,那么本题就解决了。

 

     我们设,注意这里为素数,

 

     那么,我们枚举每一个,得到,现在分情况讨论:

 

     (1)如果整除,那么得到

 

       

 

     (2)如果不整除,那么得到

 

       

代码:

  1. #include <iostream>
  2. #include <string.h>
  3. #include <stdio.h>
  4. using namespace std;
  5. typedef long long LL;
  6. const int N = 10000005;
  7. bool vis[N];
  8. int p[N];
  9. int cnt;
  10. int g[N],u[N],sum[N];
  11. void Init()
  12. {
  13. memset(vis,0,sizeof(vis));
  14. u[1] = 1;
  15. cnt = 0;
  16. for(int i=2;i<N;i++)
  17. {
  18. if(!vis[i])
  19. {
  20. p[cnt++] = i;
  21. u[i] = -1;
  22. g[i] = 1;
  23. }
  24. for(int j=0;j<cnt&&i*p[j]<N;j++)
  25. {
  26. vis[i*p[j]] = 1;
  27. if(i%p[j])
  28. {
  29. u[i*p[j]] = -u[i];
  30. g[i*p[j]] = u[i] - g[i];
  31. }
  32. else
  33. {
  34. u[i*p[j]] = 0;
  35. g[i*p[j]] = u[i];
  36. break;
  37. }
  38. }
  39. }
  40. sum[0] = 0;
  41. for(int i=1;i<N;i++)
  42. sum[i] = sum[i-1] + g[i];
  43. }
  44. int main()
  45. {
  46. Init();
  47. int T;
  48. scanf("%d",&T);
  49. while(T--)
  50. {
  51. LL n,m;
  52. cin>>n>>m;
  53. if(n > m) swap(n,m);
  54. LL ans = 0;
  55. for(int i=1,last;i<=n;i=last+1)
  56. {
  57. last = min(n/(n/i),m/(m/i));
  58. ans += (n/i)*(m/i)*(sum[last]-sum[i-1]);
  59. }
  60. cout<<ans<<endl;
  61. }
  62. return 0;
  63. }

多项式乘法运算初级版——快速傅里叶变换

快速傅里叶变换在信息学竞赛中主要用于求卷积,或者说多项式乘法。我们知道,多项式乘法的普通算法时间复杂度

,通过快速傅里叶变换可以使时间降为,那么接下来会详细介绍快速傅里叶变换的原理。

 

首先来介绍多项式的两种表示方法,即系数表示法点值表示法。从某种意义上说,这两种方法是等价的。先设

    

(1)系数表示法

 

    对于一个次数界为的多项式来说,其系数表示法就是一个由系数组成的向量,很

    明显,这样的多项式乘法运算的时间复杂度为

 

(2)点值表示法

 

    对于一个次数界为的多项式来说,其点值是个点值对所形成的集合

 

    

 

    其中各不相同,并且当时,有。可以看出一个多项式可以有多种不同的点值

    表示法,而通过这个不同的点值对可以表示一个唯一的多项式。而通过点值表示法来计算多项式的乘法,时间

    复杂度为

 

    从原则上来说,计算多项式的点值是简单易行的,因为我们只需要先选取个相异的点,然后通过秦九韶算法

    以在时间内求出所有的,实际上如果我们的选得巧妙的话,就可以加速这一过程,使其运行时间变

    为

 

    根据多项式的系数表示法求其点值表示法的过程称为求值,而根据点值表示法求其系数表示法的过程称为插值

 

    对于求卷积或者说多项式乘法运算问题,先是通过傅里叶变换对系数表示法的多项式进行求值运算,这一步的时

    间复杂度为,然后在时间内进行点值相乘,再进行插值运算。

 

那么,接下来就是我们今天的重点了,如何高效地对一个多项式进行求值运算,即将多项式的表示法变为点值表示法。

 

如果选取单位复根作为求值点,则可以通过对系数向量进行离散傅里叶变换(DFT),得到相应的点值表示。同样地

也可以通过对点值对进行逆DFT运算,获得相应的系数向量。DFT逆DFT的时间复杂度均为

 

一. 求DFT

 

    选取次单位复根作为来求点值是比较巧妙的做法。

    次单位复根是满足的复数次单位复根恰好有个,它们是,为

    了解释这一式子,利用复数幂的定义,值称为主次单位根,所有其

    它次单位复根都是次幂。

 

    次单位复根在乘法运算下形成一个群,该群的结构与加法群相同。

 

    接下来认识几个关于次单位复根的重要性质。

   

    (1)相消引理

 

        对于任何整数,有

 

    (2)折半引理

 

        如果且为偶数,则

 

    (3)求和引理

 

        对任意整数和不能被整除的非零整数,有

 

          

 

     回顾一下,我们希望计算次数界为的多项式

 

     

 

     在处的值,假定2的幂,因为给定的次数界总可以增大,如果需要,总可以添加值为零

     的新的高阶系数。假定已知的系数形式为,对,定义结果

     如下

                 

     向量是系数向量的离散傅里叶变换,写作

     通过使用一种称为快速傅里叶变换(FFT)的方法,就可以在时间内计算出,而直接

     计算的方法所需时间为FFT主要是利用单位复根的特殊性质。FFT方法运用了分治策略,它用

     中偶数下标的系数与奇数下标的系数,分别定义了两个新的次数界为的多项式

     

     则进一步有

 

     这样处的值得问题就转换为求次数界为的多项式在点

     处的值。由于在奇偶分类时导致顺序发生变化,所以需要先通过Rader算法进行

     倒位序,在FFT中最重要的一个操作是蝴蝶操作,通过蝴蝶操作可以将前半部分和后半部分的值求出。

 

题目:http://acm.hdu.edu.cn/showproblem.php?pid=1402

题意:大数乘法,需要用FFT实现。

代码:

  1. #include <iostream>
  2. #include <string.h>
  3. #include <stdio.h>
  4. #include <math.h>
  5. using namespace std;
  6. const int N = 500005;
  7. const double PI = acos(-1.0);
  8. struct Virt
  9. {
  10. double r, i;
  11. Virt(double r = 0.0,double i = 0.0)
  12. {
  13. this->r = r;
  14. this->i = i;
  15. }
  16. Virt operator + (const Virt &x)
  17. {
  18. return Virt(r + x.r, i + x.i);
  19. }
  20. Virt operator - (const Virt &x)
  21. {
  22. return Virt(r - x.r, i - x.i);
  23. }
  24. Virt operator * (const Virt &x)
  25. {
  26. return Virt(r * x.r - i * x.i, i * x.r + r * x.i);
  27. }
  28. };
  29. //雷德算法--倒位序
  30. void Rader(Virt F[], int len)
  31. {
  32. int j = len >> 1;
  33. for(int i=1; i<len-1; i++)
  34. {
  35. if(i < j) swap(F[i], F[j]);
  36. int k = len >> 1;
  37. while(j >= k)
  38. {
  39. j -= k;
  40. k >>= 1;
  41. }
  42. if(j < k) j += k;
  43. }
  44. }
  45. //FFT实现
  46. void FFT(Virt F[], int len, int on)
  47. {
  48. Rader(F, len);
  49. for(int h=2; h<=len; h<<=1) //分治后计算长度为h的DFT
  50. {
  51. Virt wn(cos(-on*2*PI/h), sin(-on*2*PI/h)); //单位复根e^(2*PI/m)用欧拉公式展开
  52. for(int j=0; j<len; j+=h)
  53. {
  54. Virt w(1,0); //旋转因子
  55. for(int k=j; k<j+h/2; k++)
  56. {
  57. Virt u = F[k];
  58. Virt t = w * F[k + h / 2];
  59. F[k] = u + t; //蝴蝶合并操作
  60. F[k + h / 2] = u - t;
  61. w = w * wn; //更新旋转因子
  62. }
  63. }
  64. }
  65. if(on == -1)
  66. for(int i=0; i<len; i++)
  67. F[i].r /= len;
  68. }
  69. //求卷积
  70. void Conv(Virt a[],Virt b[],int len)
  71. {
  72. FFT(a,len,1);
  73. FFT(b,len,1);
  74. for(int i=0; i<len; i++)
  75. a[i] = a[i]*b[i];
  76. FFT(a,len,-1);
  77. }
  78. char str1[N],str2[N];
  79. Virt va[N],vb[N];
  80. int result[N];
  81. int len;
  82. void Init(char str1[],char str2[])
  83. {
  84. int len1 = strlen(str1);
  85. int len2 = strlen(str2);
  86. len = 1;
  87. while(len < 2*len1 || len < 2*len2) len <<= 1;
  88. int i;
  89. for(i=0; i<len1; i++)
  90. {
  91. va[i].r = str1[len1-i-1] - '0';
  92. va[i].i = 0.0;
  93. }
  94. while(i < len)
  95. {
  96. va[i].r = va[i].i = 0.0;
  97. i++;
  98. }
  99. for(i=0; i<len2; i++)
  100. {
  101. vb[i].r = str2[len2-i-1] - '0';
  102. vb[i].i = 0.0;
  103. }
  104. while(i < len)
  105. {
  106. vb[i].r = vb[i].i = 0.0;
  107. i++;
  108. }
  109. }
  110. void Work()
  111. {
  112. Conv(va,vb,len);
  113. for(int i=0; i<len; i++)
  114. result[i] = va[i].r+0.5;
  115. }
  116. void Export()
  117. {
  118. for(int i=0; i<len; i++)
  119. {
  120. result[i+1] += result[i]/10;
  121. result[i] %= 10;
  122. }
  123. int high = 0;
  124. for(int i=len-1; i>=0; i--)
  125. {
  126. if(result[i])
  127. {
  128. high = i;
  129. break;
  130. }
  131. }
  132. for(int i=high; i>=0; i--)
  133. printf("%d",result[i]);
  134. puts("");
  135. }
  136. int main()
  137. {
  138. while(~scanf("%s%s",str1,str2))
  139. {
  140. Init(str1,str2);
  141. Work();
  142. Export();
  143. }
  144. return 0;
  145. }

题目:http://acm.hdu.edu.cn/showproblem.php?pid=4609

题意:给定n条长度已知的边,求能组成多少个三角形。

分析:用一个num数组来记录次数,比如num[i]表示长度为i的边有num[i]条。然后对num[]求卷积,除去本身重

     复的和对称的,然后再整理一下就好了。

代码:

  1. #include <iostream>
  2. #include <string.h>
  3. #include <algorithm>
  4. #include <stdio.h>
  5. #include <math.h>
  6. using namespace std;
  7. typedef long long LL;
  8. const int N = 400005;
  9. const double PI = acos(-1.0);
  10. struct Virt
  11. {
  12. double r,i;
  13. Virt(double r = 0.0,double i = 0.0)
  14. {
  15. this->r = r;
  16. this->i = i;
  17. }
  18. Virt operator + (const Virt &x)
  19. {
  20. return Virt(r+x.r,i+x.i);
  21. }
  22. Virt operator - (const Virt &x)
  23. {
  24. return Virt(r-x.r,i-x.i);
  25. }
  26. Virt operator * (const Virt &x)
  27. {
  28. return Virt(r*x.r-i*x.i,i*x.r+r*x.i);
  29. }
  30. };
  31. //雷德算法--倒位序
  32. void Rader(Virt F[],int len)
  33. {
  34. int j = len >> 1;
  35. for(int i=1; i<len-1; i++)
  36. {
  37. if(i < j) swap(F[i], F[j]);
  38. int k = len >> 1;
  39. while(j >= k)
  40. {
  41. j -= k;
  42. k >>= 1;
  43. }
  44. if(j < k) j += k;
  45. }
  46. }
  47. //FFT实现
  48. void FFT(Virt F[],int len,int on)
  49. {
  50. Rader(F,len);
  51. for(int h=2; h<=len; h<<=1) //分治后计算长度为h的DFT
  52. {
  53. Virt wn(cos(-on*2*PI/h),sin(-on*2*PI/h)); //单位复根e^(2*PI/m)用欧拉公式展开
  54. for(int j=0; j<len; j+=h)
  55. {
  56. Virt w(1,0); //旋转因子
  57. for(int k=j; k<j+h/2; k++)
  58. {
  59. Virt u = F[k];
  60. Virt t = w*F[k+h/2];
  61. F[k] = u+t; //蝴蝶合并操作
  62. F[k+h/2] = u-t;
  63. w = w*wn; //更新旋转因子
  64. }
  65. }
  66. }
  67. if(on == -1)
  68. for(int i=0; i<len; i++)
  69. F[i].r /= len;
  70. }
  71. //求卷积
  72. void Conv(Virt F[],int len)
  73. {
  74. FFT(F,len,1);
  75. for(int i=0; i<len; i++)
  76. F[i] = F[i]*F[i];
  77. FFT(F,len,-1);
  78. }
  79. int a[N];
  80. Virt F[N];
  81. LL num[N],sum[N];
  82. int len,n;
  83. void Init()
  84. {
  85. memset(num,0,sizeof(num));
  86. scanf("%d",&n);
  87. for(int i=0; i<n; i++)
  88. {
  89. scanf("%d",&a[i]);
  90. num[a[i]]++;
  91. }
  92. sort(a, a + n);
  93. int len1 = a[n-1] + 1;
  94. len = 1;
  95. while(len < len1*2) len <<= 1;
  96. for(int i=0; i<len1; i++)
  97. F[i] = Virt(num[i],0);
  98. for(int i=len1; i<len; i++)
  99. F[i] = Virt(0,0);
  100. }
  101. void Work()
  102. {
  103. Conv(F,len);
  104. for(int i=0; i<len; i++)
  105. num[i] = (LL)(F[i].r+0.5);
  106. len = a[n-1]*2;
  107. for(int i=0; i<n; i++)
  108. num[a[i]+a[i]]--;
  109. for(int i=1; i<=len; i++)
  110. num[i] >>= 1;
  111. sum[0] = 0;
  112. for(int i=1; i<=len; i++)
  113. sum[i] = sum[i-1] + num[i];
  114. LL cnt = 0;
  115. for(int i=0; i<n; i++)
  116. {
  117. cnt+=sum[len]-sum[a[i]];
  118. //减掉一个取大,一个取小的
  119. cnt-=(LL)(n-1-i)*i;
  120. //减掉一个取本身,另外一个取其它
  121. cnt-=(n-1);
  122. //减掉大于它的取两个的组合
  123. cnt-=(LL)(n-1-i)*(n-i-2)/2;
  124. }
  125. LL tot = (LL)n*(n-1)*(n-2)/6;
  126. printf("%.7lf\n",(double)cnt/tot);
  127. }
  128. int main()
  129. {
  130. int T;
  131. scanf("%d",&T);
  132. while(T--)
  133. {
  134. Init();
  135. Work();
  136. }
  137. return 0;
  138. }

多项式乘法运算终极版——NTT(快速数论变换)

在上一篇文章中 http://blog.csdn.net/acdreamers/article/details/39005227 介绍了用快速傅里叶变

换来求多项式的乘法。可以发现它是利用了单位复根的特殊性质,大大减少了运算,但是这种做法是对复数系数的矩阵

加以处理,每个复数系数的实部和虚部是一个正弦及余弦函数,因此大部分系数都是浮点数,我们必须做复数及浮点数

的计算,计算量会比较大,而且浮点数的计算可能会导致误差增大。

 

今天,我将来介绍另一种计算多项式乘法的算法,叫做快速数论变换(NTT),在离散正交变换的理论中,已经证明在

复数域内,具有循环卷积特性的唯一变换是DFT,所以在复数域中不存在具有循环卷积性质的更简单的离散正交变换。

因此提出了以数论为基础的具有循环卷积性质的快速数论变换

 

回忆复数向量,其离散傅里叶变换公式如下

 

   

 

离散傅里叶逆变换公式为

 

   

 

今天的快速数论变换(NTT)是在上进行的,在快速傅里叶变换(FFT)中,通过次单位复根来运算的,即满

,而对于快速数论变换来说,则是可以将看成是的等价,这里是模素数

的原根(由于是素数,那么原根一定存在)。即

 

        

 

所以综上,我们得到数论变换的公式如下

 

    

 

数论变换的逆变换公式为

 

    

 

这样就把复数对应到一个整数,之后一切都是在系统内考虑。

 

上述数论变换(NTT)公式中,要求是素数且必须是的因子。由于经常是2的方幂,所以可以构造形

的素数。通常来说可以选择费马素数,这样的变换叫做费马数数论变换

 

这里我们选择,这样得到模的原根值为

 

题目:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1028

分析:题目意思就是大数相乘,此处用快速数论变换(NTT)实现。

代码:

  1. #include <iostream>
  2. #include <string.h>
  3. #include <stdio.h>
  4. using namespace std;
  5. typedef long long LL;
  6. const int N = 1 << 18;
  7. const int P = (479 << 21) + 1;
  8. const int G = 3;
  9. const int NUM = 20;
  10. LL wn[NUM];
  11. LL a[N], b[N];
  12. char A[N], B[N];
  13. LL quick_mod(LL a, LL b, LL m)
  14. {
  15. LL ans = 1;
  16. a %= m;
  17. while(b)
  18. {
  19. if(b & 1)
  20. {
  21. ans = ans * a % m;
  22. b--;
  23. }
  24. b >>= 1;
  25. a = a * a % m;
  26. }
  27. return ans;
  28. }
  29. void GetWn()
  30. {
  31. for(int i=0; i<NUM; i++)
  32. {
  33. int t = 1 << i;
  34. wn[i] = quick_mod(G, (P - 1) / t, P);
  35. }
  36. }
  37. void Prepare(char A[], char B[], LL a[], LL b[], int &len)
  38. {
  39. len = 1;
  40. int len_A = strlen(A);
  41. int len_B = strlen(B);
  42. while(len <= 2 * len_A || len <= 2 * len_B) len <<= 1;
  43. for(int i=0; i<len_A; i++)
  44. A[len - 1 - i] = A[len_A - 1 - i];
  45. for(int i=0; i<len - len_A; i++)
  46. A[i] = '0';
  47. for(int i=0; i<len_B; i++)
  48. B[len - 1 - i] = B[len_B - 1 - i];
  49. for(int i=0; i<len - len_B; i++)
  50. B[i] = '0';
  51. for(int i=0; i<len; i++)
  52. a[len - 1 - i] = A[i] - '0';
  53. for(int i=0; i<len; i++)
  54. b[len - 1 - i] = B[i] - '0';
  55. }
  56. void Rader(LL a[], int len)
  57. {
  58. int j = len >> 1;
  59. for(int i=1; i<len-1; i++)
  60. {
  61. if(i < j) swap(a[i], a[j]);
  62. int k = len >> 1;
  63. while(j >= k)
  64. {
  65. j -= k;
  66. k >>= 1;
  67. }
  68. if(j < k) j += k;
  69. }
  70. }
  71. void NTT(LL a[], int len, int on)
  72. {
  73. Rader(a, len);
  74. int id = 0;
  75. for(int h = 2; h <= len; h <<= 1)
  76. {
  77. id++;
  78. for(int j = 0; j < len; j += h)
  79. {
  80. LL w = 1;
  81. for(int k = j; k < j + h / 2; k++)
  82. {
  83. LL u = a[k] % P;
  84. LL t = w * (a[k + h / 2] % P) % P;
  85. a[k] = (u + t) % P;
  86. a[k + h / 2] = ((u - t) % P + P) % P;
  87. w = w * wn[id] % P;
  88. }
  89. }
  90. }
  91. if(on == -1)
  92. {
  93. for(int i = 1; i < len / 2; i++)
  94. swap(a[i], a[len - i]);
  95. LL Inv = quick_mod(len, P - 2, P);
  96. for(int i = 0; i < len; i++)
  97. a[i] = a[i] % P * Inv % P;
  98. }
  99. }
  100. void Conv(LL a[], LL b[], int n)
  101. {
  102. NTT(a, n, 1);
  103. NTT(b, n, 1);
  104. for(int i = 0; i < n; i++)
  105. a[i] = a[i] * b[i] % P;
  106. NTT(a, n, -1);
  107. }
  108. void Transfer(LL a[], int n)
  109. {
  110. int t = 0;
  111. for(int i = 0; i < n; i++)
  112. {
  113. a[i] += t;
  114. if(a[i] > 9)
  115. {
  116. t = a[i] / 10;
  117. a[i] %= 10;
  118. }
  119. else t = 0;
  120. }
  121. }
  122. void Print(LL a[], int n)
  123. {
  124. bool flag = 1;
  125. for(int i = n - 1; i >= 0; i--)
  126. {
  127. if(a[i] != 0 && flag)
  128. {
  129. printf("%d", a[i]);
  130. flag = 0;
  131. }
  132. else if(!flag)
  133. printf("%d", a[i]);
  134. }
  135. puts("");
  136. }
  137. int main()
  138. {
  139. GetWn();
  140. while(scanf("%s%s", A, B)!=EOF)
  141. {
  142. int len;
  143. Prepare(A, B, a, b, len);
  144. Conv(a, b, len);
  145. Transfer(a, len);
  146. Print(a, len);
  147. }
  148. return 0;
  149. }


转载于:https://www.cnblogs.com/tham/p/6827175.html

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/IT小白/article/detail/487689
推荐阅读
相关标签
  

闽ICP备14008679号