信息
- ID
- 191
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 3
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者
x=910A−1,y=9109−1。
先考虑计算 gcd(x,y)。
有结论
gcd(xn−1,xm−1)=xgcd(n,m)−1以下给出证明
不妨假设 n≥m,因为 gcd(xm,xm−1)=1
$$\gcd(x^n-1,x^m-1)=\gcd(x^m(x^{n-m}-1)+x^m-1,x^m-1)=\gcd(x^m(x^{n-m}-1),x^m-1)$$因此
gcd(xn−1,xm−1)=gcd((xn−m−1),xm−1)类比辗转相除法的过程,最终
gcd(xn−1,xm−1)=xgcd(n,m)−1c=gcd(A,B),ac=A,bc=B
答案为
$$\frac{10^c-1}{9} \times \frac{10^{ac}-1}{10^c-1}\times \frac{10^{bc}-1}{10^c-1}$$10ac−1=(10c−1)i=0∑a−110ic可以利用快速幂直接求解,具体实现参考代码: