P11036 【MX-X3-T3】「RiOI-4」GCD 与 LCM 问题 不妨令 b=1, gcd(c,d)=gb=1,\ gcd(c,d)=g，所以 a+c+d=cdga+c+d=\frac{cd}{g}。 设 a=2p⋅k (2∤k), c=xg, d=yg (gcd(x,y)=1)a=2^p \cdot k \ (2\nmid k), \ c=xg,\ d=yg\ (gcd(x,y)=1)，那么有：2p⋅k=g(xy−x−y)2^p\cdot k=g(xy-x-y)。 不妨令 g=1g=1，若 p=0p=0，解方程得一组特解为：x=2, y=k+2x=2,\ y=k+2。 根据特解再把 2p2^p 乘回去即可，代码： #include using namespace std; int T,a,x; int main(){ scanf("%d",&T); while(T--){ x=1,scanf("%d",&a); while(a%2==0) a/=2,x*=2; printf("1 %d %d\n",2*x,(a+2)*x); } return 0; } `#include using namespace std; int T,a,x; int main(){ scanf("%d",&T); while(T--){ x=1,scanf("%d",&a); while(a%2==0) a/=2,x*=2; printf("1 %d %d\n",2*x,(a+2)*x); } return 0; }`
P11036 【MX-X3-T3】「RiOI-4」GCD 与 LCM 问题
笔记