1 条题解

  • 0
    @ 2026-11-15 21:04:07

    题目分析

    x=10A−19,y=109−19x=\frac{10^A-1}{9},y=\frac{10^9-1}{9}。

    先考虑计算 gcd⁡(x,y)\gcd(x,y)。

    有结论

    gcd⁡(xn−1,xm−1)=xgcd⁡(n,m)−1\gcd(x^n-1,x^m-1)=x^{\gcd(n,m)}-1

    以下给出证明

    不妨假设 n≥mn \geq m,因为 gcd⁡(xm,xm−1)=1\gcd(x^m,x^m-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(x^n-1,x^m-1)=\gcd((x^{n-m}-1),x^m-1)

    类比辗转相除法的过程,最终

    gcd⁡(xn−1,xm−1)=xgcd⁡(n,m)−1\gcd(x^n-1,x^m-1)=x^{\gcd(n,m)}-1

    c=gcd⁡(A,B),ac=A,bc=Bc=\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=0a−110ic10^{ac}-1=(10^c-1)\sum_{i=0}^{a-1} 10^{ic}

    可以利用快速幂直接求解,具体实现参考代码:

    • 1

    信息

    ID
    191
    时间
    1000ms
    内存
    512MiB
    难度
    3
    标签
    递交数
    1
    已通过
    1
    上传者