1 条题解
-
0
注意到不管是多少的都输出1即可(结束(bushi
下面是严格证明
首先证明
对于k个不全为0的数, 有$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)})$
设
则有
那么
设存在一个大于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$
则对于上面结论有 ,,
可得 $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
- 上传者