P1029 [NOIP 2001 普及组] 最大公约数和最小公倍数问题 题解（代刷一百系列）

P1029 [NOIP 2001 普及组] 最大公约数和最小公倍数问题 - 洛谷

最大公约数：gcd（int a,int b）//欧几里得算法时间复杂度O(log(min(a,b)));

最大公倍数：lcm(int a,int b)

a*b = gcd(int a,int b)*lcm(int a,int b);

#include<bits/stdc++.h> using namespace std; const int N = 1e5+9; const int mod = 1e9+9; using ll = long long; const char el = '\n'; #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) int arr[N]; int gcd(int a,int b) { return (b==0?a:gcd(b,a%b)); } int lcm(int a,int b) { return a*b/gcd(a,b); } //两个数的乘积等于最大公约数和最小公倍数的乘积 int main() { IOS; int x,y;cin>>x>>y; int ans = 0; for(int i = x;i<=y;i++) { int j = x*y/i; if(lcm(i,j)==y&&gcd(i,j)==x) ans++; } cout<<ans; }