1 条题解

  • 0
    @ 2025-6-28 11:45:07
    注意到不管a,b,ca,b,c是多少的都输出1即可(结束(bushi

    下面是严格证明

    首先证明

    对于k个不全为0的数,a1,a2,a3,.....,aka_1,a_2,a_3,.....,a_k 有$gcd( \frac{a_1}{gcd(a_1,a_2,...,a_k)},\frac{a_2}{gcd(a_1,a_2,...,a_k)},...\frac{a_k}{gcd(a_1,a_2,...,a_k)})$

    d=gcd(a1,a2,...,ak)d=gcd(a_1,a_2,...,a_k)

    则有dai(i=1,2,3...k)d|a_i(i=1,2,3...k)

    那么ai=dmi(i=1,2,3...k)a_i=dm_i(i=1,2,3...k)

    设存在一个大于1的数kk使得 kmik|m_i

    则有kmiaikm_i|a_i

    显然与

    d=gcd(a1,a2,...,ak)d=gcd(a_1,a_2,...,a_k)矛盾

    那么

    gcd(m1,m2,...,mk)=1gcd(m_1,m_2,...,m_k)=1得证

    即$gcd( \frac{a_1}{gcd(a_1,a_2,...,a_k)},\frac{a_2}{gcd(a_1,a_2,...,a_k)},...\frac{a_k}{gcd(a_1,a_2,...,a_k)})$得证

    其次证明

    $gcd(\frac{a}{gcd(a,c)},\frac{b}{gcd(b,a)},\frac{c}{gcd(b,c)})=1$

    则对于上面结论有 agcd(a,c)agcd(a,b,c)\frac{a}{gcd(a,c)}|\frac{a}{gcd(a,b,c)},bgcd(a,b)bgcd(a,b,c)\frac{b}{gcd(a,b)}|\frac{b}{gcd(a,b,c)}, cgcd(b,c)cgcd(a,b,c)\frac{c}{gcd(b,c)}|\frac{c}{gcd(a,b,c)}

    可得 $gcd(\frac{a}{gcd(a,c)},\frac{b}{gcd(a,b)},\frac{c}{gcd(b,c)})|gcd(\frac{a}{gcd(a,b,c)}\frac{b}{gcd(a,b,c)}\frac{c}{gcd(a,b,c)})=1$

    整除的性质可得 $gcd(\frac{a}{gcd(a,c)},\frac{b}{gcd(b,a)},\frac{c}{gcd(b,c)})=1$ 证毕

    • 1

    信息

    ID
    16
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    (无)
    递交数
    46
    已通过
    20
    上传者