题目名称：最大公约数和最小公倍数问题
来源：2001年NOIP普及组
# 链接
## 博客链接
- [博客园](https://www.cnblogs.com/Alvin-Tree/p/11563042.html)
- [CSDN](https://blog.csdn.net/weixin_43890363/article/details/100937310)
- [洛谷博客](https://www.luogu.org/blog/131abc155-7341-6424/solution-p1029)
- [洛谷题解](https://www.luogu.org/problemnew/solution/P1029)
## 题目链接
- [Vijos](https://vijos.org/p/1131)
- [洛谷(P1029)](https://www.luogu.org/problem/P1029)
- [入门OJ(1172)](https://begin.lydsy.com/JudgeOnline/problem.php?id=1172)
# 题解
约定$D=min(x_0,y_0),M=max(x_0,y_0)$
`情况1：`
$M \mod D\neq0$
显然，无解。
`情况2：`
$M \mod D=0$
推一波
$$
\because (P,Q)=D,[P,Q]=M
$$
$$
\therefore P\times Q=(P,Q)[P,Q]=D\times M
$$
$$
p=P\div D,q=Q\div D,prod=D\div M
$$
$$
\therefore p\times q=prod\&(p,q)=1
$$
当然，暴力枚举$p$就可以通过此题，时间复杂度$O(\sqrt{prod}\times \log(\sqrt{prod}))$。
但是这次笔者要将一个更优的解法。
由推出来的式子可得，我们就要求有多少对$prod$的因数互质。
现将$prod$分解质因子得到$prod$有$n$种质因子。
对于质因子$d$，要么只是$p$的质因子，要么只是$q$的质因子（如果$p$和$q$同时拥有这个质因子$d$，那么$(p,q)\neq 1$），并且$d$至少要是其中一个的因数（否则$p\times q\neq prod$）。
所以说其中每种质因子都有两种可能，则答案是$2^n$。
时间复杂度$O(玄学)$，（最坏$O(\sqrt{prod})$，最好$O(\log(prod))$）
```cpp
//C++
#include<bits/locale_facets.h>
#include<stdio.h>
#define forto(name,i,d,u) for(name i=d;i<=u;i++)
inline void output(long long o);
inline long long input();
int main()
{
short numeral=0;
int x=input(),y=input();
if(y%x)return putchar('0'),0;
y/=x;
forto(int,i,2,y/i)
if(!(y%i))
{
numeral++;
while(!(y%i))y/=i;
}
if(y>1)numeral++;
output(1<<numeral);
return 0;
}
inline void output(long long o)
{
if(o<0)putchar('-'),o=-o;
if(o>=10)output(o/10);
putchar(o%10^'0');
}
inline long long input()
{
bool minus=false;
char now=getchar();
long long i=0;
for(;!isdigit(now);now=getchar())
if(now=='-')minus=!minus;
for(;isdigit(now);now=getchar())i=(i<<3)+(i<<1)+(now^'0');
return minus?-i:i;
}
```
```pascal
//pascal
var
numeral:1..30;
x:2..100000;
i,y:1..1000000;
begin
readln(x,y);
if y mod x>0 then
begin
write('0');
halt;
end;
y:=y div x;
i:=2;
while i<=y div i do
begin
if y mod i=0 then
begin
inc(numeral);
while y mod i=0 do y:=y div i;
end;
inc(i);
end;
if y>1 then inc(numeral);
write(1 shl numeral);
end.
```