洛谷P1029
https://www.luogu.com.cn/problem/P1029#ide
P1029 [NOIP 2001 普及组] 最大公约数和最小公倍数问题
题目描述
输入两个正整数 x_0, y_0，求出满足下列条件的 P, Q 的个数：
1. $P,Q$ 是正整数。
2. 要求 P, Q 以 x_0 为最大公约数，以 y_0 为最小公倍数。
试求：满足条件的所有可能的 P, Q 的个数。
输入格式
一行两个正整数 x_0, y_0。
输出格式
一行一个数，表示求出满足条件的 $P, Q$ 的个数。
## 输入输出样例 #1
### 输入 #1
```
3 60
```
### 输出 #1
```
4
```
## 说明/提示
$P,Q$ 有 $4$ 种：
1. $3, 60$。
2. $15, 12$。
3. $12, 15$。
4. $60, 3$。
对于 $100\%$ 的数据，$2 \le x_0, y_0 \le {10}^5$。
**【题目来源】**
NOIP 2001 普及组第二题
当然可以暴力循环解决问题，这是暴力代码，甚至还不完全对，没有考虑到输入x=y的情况。耗时你就看吧
#include<iostream>
using namespace std;
int maxgy(int a,int b)//返回最大公约数
{
if(b==0)
return a;
else return maxgy(b,a%b);
}
int mingb(int a,int b,int gy)
{
return a*b/gy;
}
int main()
{
int x0,y0;
while(cin>>x0>>y0)
{ int count=0;
for(long long i=2;i<=100000;i++)
{
for(long long j=i;j<=100000;j++)
{
if(maxgy(i,j)==x0 && mingb(i,j,maxgy(i,j))==y0)
count+=2;
}
}
cout<<count<<endl;
}
}
花了二十五分钟
关键是能否理解这个数学关系
首先如果想让p，q满足x0是他们的最大公约数，其最小公倍数又是y0，先要知道一个条件
两个数之积等于其最大公约数与最小公倍数之积
即p*q=x0*y0
知道这个之后，我们就可以只循环一次，从1循环到sqrt（x0*y0）
为什么，我们在这个范围内选择一个i
如果他满足 x0*y0%i==0 那就说明i*j（j是另一个数）=x0*y0，即两个数之积等于其最大公约数与最小公倍数之积。但是现在的问题是，我们既不知道x0是否是i和j的最大公约数，也不知道y0是否是i和j的最小公倍数。而我们只需要求出任意一个，我们假如可以知道x0是i和j的最大公约数，那么根据i*j=x0*y0，就一定知道y0是i和j的最小公倍数，因为两个数之积等于其最大公约数与最小公倍数之积。而给定两个数求最小公倍数也需要我们先求出最大公约数，所以我们就将另一个条件设为i与j的最大公约数等于x0，结合起来就是n%i==0 && maxgy(i,n/i)==x0。
为什么只需要判断到sqrt（x0*y0）就可以了？因为这个ij是成对出现的，即，如果i*j=x0*y0，那么一定有j*i=x0*y0，每当我们找到一组数据直接让结果+2即可，而这个对称轴就是sqrt（x0*y0）
当i=sqrt（x0*y0）时，j=i=sqrt（x0*y0）。同时，i与j的最大公约数是i，最小公倍数是i，即i=j=x0=y0，所以如果输入的x0=y0，就会出现对称轴的情况，此时count只需+1，而循环中默认+2，所以我们在输入x0=y0时直接先将count-1就好了
#include<iostream>
#include<math.h>
using namespace std;
long long maxgy(long long a,long long b)//返回最大公约数
{
if(b==0)
return a;
else return maxgy(b,a%b);
}
long long mingb(long long a,long long b,long long gy)
{
return a*b/gy;
}
int main()
{
long long x0,y0;
while(cin>>x0>>y0)
{ int count=0;
long long n=x0*y0;//
if(x0==y0)
count--;
for(long long i=1;i<=sqrt(n);i++)
{
if(n%i==0 && maxgy(i,n/i)==x0)
count+=2;
}
cout<<count<<endl;
}
}