题目

牛客网：小红的 gcd

题目分析

我们知道，求gcd就用欧几里得算法（辗转相除法）：gcd(a,b)=gcd(b,a mod b)。但是这题的a非常大，最大是一个1e6位数，无法使用任何数据类型存储。如果使用高精度计算的话，需要逐位计算，会超时。

一个十进制数字例如 $123$ 是可以拆分成 $1\ast 10^2+2\ast 10^1+3\ast 10^0$，而且欧几里得算法会不断对a取模，我们又知道可以在任意位置取模的性质。根据这两个特性，我们就可以通过秦九绍算法将 a 这个数字拆分10的一元多项式，在逐位计算a的同时计算a mod b。

$$a\mathrm{mod}b=\left(\sum _{i=0}^{n-1}{d}_i\times 10^i\right)\mathrm{mod}b$$
其中 $d_i$ 是 $a$ 的第 $i$ 位数字。

秦九绍算法

是一种多项式求值的高效算法。它的核心思想是通过嵌套乘法和加法来减少计算次数，将多项式求值的时间复杂度$O(n^2)$优化到$O(n)$。

对于一个多项式：$$f(x)=a_n{x}^n+a_{n-1}{x}^{n-1}+a_{n-2}{x}^{n-2}+\cdots +a_1{x}^1+a_0{x}^0$$

秦九韶算法将其改写为嵌套形式：

$$\begin{array}{rl}f(x)& =(a_n{x}^{n-1}+a_{n-1}{x}^{n-2}+a_{n-2}{x}^{n-3}+\cdots +a_1)x+a_0\\ & =\left((a_n{x}^{n-2}+a_{n-1}{x}^{n-3}+a_{n-2}{x}^{n-4}+\cdots +a_2)x+a_1\right)x+a_0\\ & ⋮\\ & =\left(\dots \left((a_{n}x+a_{n-1})x+a_{n-2}\right)x+\cdots +a_2\right)x+a_1)x+a_0\end{array}$$

示例：

AC代码

#include<iostream> using namespace std;string a; 
int b;int calc()
{long long ret = 0;for(auto ch:a){ret = (ret * 10 + ch - '0') % b;}return ret;
}int gcd(int a, int b)
{return b == 0 ? a : gcd(b,a%b);	
}int main()
{cin >> a >> b;cout << gcd(calc(),b) << endl;return 0;
}