cf1366 D. Two Divisors

2022/4/19 6:13:19

编程Tag： GCD 因子 d2 题意 two d1 implies cf1366 Divisors

本文主要是介绍cf1366 D. Two Divisors，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题意：

找 x 的两个大于 1 的因子 d1 和 d2，使得 \(\gcd(d1+d2,x)=1\)

思路：

性质：\(\gcd(a,b)=\gcd(a+b,b)\)

所以，

\(\gcd (x,y)=1=\gcd(x+y,x)=\gcd(x+y,y)\implies \gcd(x+y,xy)=1\)

找 x 的最小素因子和它的次数 \(p^k\)，答案是 \(p^k,x/p^k\)

这篇关于cf1366 D. Two Divisors的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

更多>