P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题 题解

[题目传送门]了解一下？(https://www.luogu.com.cn/problem/P1029) [AC记录]再了解一下？(https://www.luogu.com.cn/record/40439298) 众所周知，两个数相乘=这两个数的最大公约和最小公倍数相乘，so # 上代码！！！ ```cpp #include<bits/stdc++.h> using namespace std; int gcd(int a,int b)//最大公约数 { if(a==0) { return b; } return gcd(b%a,a); } int main() { int x,y,i,j,n=0,k;//n为答案 cin>>x>>y; for(i=x;i<=y;i++)最大公约数肯定要小于等于原数，最小公倍数肯定要大于等于原数，所以范围就出来了 { if((x*y)%i==0)//如果两个数相乘=这两个数的最大公约和最小公倍数相乘，转化一下就是其中一个数=这两个数的最大公约和最小公倍数相乘/另一个数，前提是除得开 { j=(x*y)/i; if(gcd(i,j)==x)//最大公约数是x n++;//答案+1 } } cout<<n; return 0; } ```