[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\n", 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\n", ans);return 0;
}