题解 P1029 【最大公约数和最小公倍数问题】

因为 $x_0=gcd(P,Q)$，故 $x_0|P,x_0|Q$。 所以设 $P=ax_0,Q=bx_0$。 假设 $a,b$ 不互质，则设 $x_1=gcd(a,b)\not=1$，则 $gcd(P,Q)=gcd(ax_0,bx_0)=x_0gcd(a,b)=x_0x_1\not=x_0$，不符合题意，故假设不成立，$a,b$ 互质。 由于 $y_0=lcm(P,Q)=lcm(ax_0,bx_0)=abx_0$，所以 $ab=\Large\frac{y_0}{x_0}$。 由于 $P=ax_0,Q=bx_0$，所以 $a,b$ 所有可能的情况与 $P,Q$ 所有可能的情况一一对应，所以只需要求出 $a,b$ 可能的情况数即可。 若 $x_0$ 不能整除 $y_0$ ，则无解，方案数为零。 若 $\frac{y_0}{x_0}=k$，将 $k$ 分解质因数得：$d_1^{c_1}\times d_2^{c_2}\times ...\times d_m^{c_m}$。 则 $ab=d_1^{c_1}\times d_2^{c_2}\times ...\times d_m^{c_m}$，由于 $a,b$ 互质，即 $a,b$没有公共的质因子。故对于每一个质因子，不管次数是多少，要么全都属于 $a$，要么全都属于 $b$。 相当于共 $m$ 个不同的物品，放入两个不同的箱子，由第二类斯特林数可以得知方案数为 $2^m-2$。 再观察样例说明可以得知还有一种特殊情况，即 $a=1$ 或 $b=1$。对于这种情况只需要在结果后面加二即可，即答案为 $2^m$ 。 综上，只需要求出 $\frac{y_0}{x_0}$ 的质因数个数 $m$ ，再求出 $2^m$ 即可。 计算质因数个个数平均时间复杂度是多少呢？ ~~我也不知道~~。于是我写了个程序验证平均复杂度：  大约是 $O(69)$。 再加上快速幂的时间复杂度 $O(logm)$，而 $m\leq log{\frac{y_0}{x_0}}$，故时间复杂度约为 $O(loglog\frac{y_0}{x_0})$。 综上，时间复杂度约为 $O(69+loglog\frac{y_0}{x_0})$ (注：因为快速幂的底数为 $2$，所以对于 C++ 的 OIer 来说可以采用位运算 $O(1)$ 得到。) $Code:$ ```cpp #include<iostream> #include<cstdio> using namespace std; int x,y,cnt; int ksm(int a,int b){ int ans=1; for(;b;a*=a,b>>=1)if(b&1)ans*=a; return ans; } int main(){ scanf("%d%d",&x,&y); if(x==y)return printf("1"),0; if(y%x==0)y/=x; else return printf("0"),0; for(int i=2;i*i<=y;++i){ if(y%i==0)++cnt; while(y%i==0)y/=i; } if(y!=1)++cnt; printf("%d",ksm(2,cnt));//printf("%d",1<<cnt); return 0; } ```