題目

牛客網：小紅的 gcd

題目分析

我們知道，求gcd就用歐幾里得算法（輾轉相除法）：gcd(a,b)=gcd(b,a mod b)。但是這題的a非常大，最大是一個1e6位數，無法使用任何數據類型存儲。如果使用高精度計算的話，需要逐位計算，會超時。

一個十進制數字例如 $123$ 是可以拆分成 $1?10^2+2?10^1+3?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}+?+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}+?+a_1)x+a_0\\ & =\left((a_n{x}^{n?2}+a_{n?1}{x}^{n?3}+a_{n?2}{x}^{n?4}+?+a_2)x+a_1\right)x+a_0\\ & ?\\ & =\left(\dots \left((a_{n}x+a_{n?1})x+a_{n?2}\right)x+?+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;
}