[luoguP1029] 最大公约数和最小公倍数问题（数论） 一.暴力枚举（加了点优化） 二.降维
#include <cstdio>
int x, y, ans;
inline int gcd(int x, int y)
{
return !y ? x : gcd(y, x % y);
}
inline int lcm(int x, int y)
{
return x / gcd(x, y) * y;
}
int main()
{
int i, j;
scanf("%d %d", &x, &y);
for(i = x; i <= (y >> 1); i += x)
for(j = i; j <= (y >> 1); j += x)
if(gcd(i, j) == x && lcm(i, j) == y)
ans++;
for(i = x; i <= y; i += x)
if(gcd(i, y) == x && !(y % i))
ans++;
ans <<= 1;
printf("%d
", ans);
return 0;
}
二.降维
通过关系式
- x * y == gcd(x, y) * lcm(x, y)
可以枚举 x，根据等式求 y
#include <cstdio>
int x, y, ans;
inline int gcd(int x, int y)
{
return !y ? x : gcd(y, x % y);
}
inline int lcm(int x, int y)
{
return x / gcd(x, y) * y;
}
int main()
{
int i, j;
scanf("%d %d", &x, &y);
for(i = x; i <= y; i++)
{
j = x * y / i;
if(gcd(i, j) == x && lcm(i, j) == y) ans++;
}
printf("%d
", ans);
return 0;
}