网硕互联帮助中心题目
牛客网：小红的 gcd 
题目分析
我们知道，求gcd就用欧几里得算法（辗转相除法）：gcd(a,b)=gcd(b,a mod b)。但是这题的a非常大，最大是一个1e6位数，无法使用任何数据类型存储。如果使用高精度计算的话，需要逐位计算，会超时。
一个十进制数字例如
123
123
123 是可以拆分成
1
∗
10
2
+
2
∗
10
1
+
3
∗
10
0
1*10^2 + 2*10^1 + 3*10^0
1∗102+2∗101+3∗100，而且欧几里得算法会不断对a取模，我们又知道可以在任意位置取模的性质。根据这两个特性，我们就可以通过秦九绍算法将 a 这个数字拆分10的一元多项式，在逐位计算a的同时计算a mod b。
a
m
o
d
b
=
(
∑
i
=
0
n
−
1
d
i
×
10
i
)
m
o
d
b
a \\bmod b = \\left( \\sum_{i=0}^{n-1} d_i \\times 10^i \\right) \\bmod b
amodb=(i=0∑n−1di×10i)modb 其中
d
i
d_i
di 是
a
a
a 的第
i
i
i 位数字。
秦九绍算法
是一种多项式求值的高效算法。它的核心思想是通过嵌套乘法和加法来减少计算次数，将多项式求值的时间复杂度
O
(
n
2
)
O(n^2)
O(n2)优化到
O
(
n
)
O(n)
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
f(x) = a_n x^n + a_{n-1} x^{n-1} + a_{n-2} x^{n-2} + \\dots + a_1 x^1 + a_0 x^0
f(x)=anxn+an−1xn−1+an−2xn−2+⋯+a1x1+a0x0
秦九韶算法将其改写为嵌套形式：
f
(
x
)
=
(
a
n
x
n
−
1
+
a
n
−
1
x
n
−
2
+
a
n
−
2
x
n
−
3
+
⋯
+
a
1
)
x
+
a
0
=
(
(
a
n
x
n
−
2
+
a
n
−
1
x
n
−
3
+
a
n
−
2
x
n
−
4
+
⋯
+
a
2
)
x
+
a
1
)
x
+
a
0
⋮
=
(
…
(
(
a
n
x
+
a
n
−
1
)
x
+
a
n
−
2
)
x
+
⋯
+
a
2
)
x
+
a
1
)
x
+
a
0
\\begin{aligned} f(x) &= (a_n x^{n-1} + a_{n-1} x^{n-2} + a_{n-2} x^{n-3} + \\dots + a_1 )x + a_0 \\\\ &= \\left( (a_n x^{n-2} + a_{n-1} x^{n-3} + a_{n-2} x^{n-4} + \\dots + a_2 )x + a_1 \\right)x + a_0 \\\\ &\\ \\, \\vdots \\\\ &= \\left( \\dots \\left( (a_n x + a_{n-1} )x + a_{n-2} \\right)x + \\dots + a_2 \\right)x + a_1 )x + a_0 \\end{aligned}
f(x)=(anxn−1+an−1xn−2+an−2xn−3+⋯+a1)x+a0=((anxn−2+an−1xn−3+an−2xn−4+⋯+a2)x+a1)x+a0 ⋮=(…((anx+an−1)x+an−2)x+⋯+a2)x+a1)x+a0
示例： 
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;
}
评论前必须登录！
注册