在复习约数定理和一些推论的时候又发现了这道好题
题意
已知正整数a_0, a_1, b_0, b_2,求x满足:
gcd(x,a_0) = a_1 且 lcm(x, b_0) = b_1
求这样的x的个数
Sol1
最大公约数和最小公倍数有一个这样的性质:a * b = gcd(a, b) * lcm(a, b)
那么题目中的条件2可以推出:
x * b_0 = lcm(x,b_0) * gcd(x, b_0) = b_1 * gcd(x, b0)
那么x = \frac{b_1}{b_0} * gcd(x,b_0)
那么我们可以在[1, \sqrt{b_0}]的范围内枚举g = gcd(x, b_0)
那么x = \frac{b_1}{b_0} * d 和 x = \frac{b_1}{b_0} * (n / d)都应该满足题目的两个条件
注意有可能会有一个> \sqrt{b0} 的因子,注意特别判断
代码贴上:
#include
using namespace std;
int T, a0, a1, b0, b1;
inline int read()
{
char ch = getchar();
int f = 1, x = 0;
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
return x * f;
}
inline int gcd(int a, int b)
{
if (!b) { return a; }
else return gcd(b, a % b);
}
int main()
{
T = read();
while (T --) {
a0 = read(), a1 = read(), b0 = read(), b1 = read();
if (b1 % b0 != 0) {
puts("0");
continue;
}
int cnt = 0;
for (int i = 1; i * i < b0; ++ i) {
if (b0 % i == 0) {
int x = (b1 / b0) * i;
if (gcd(x, b0) == i && gcd(x, a0) == a1) cnt ++;
x = b1 / b0 * (b0 / i);
if (gcd(x, b0) == b0 / i && gcd(x, a0) == a1) cnt ++;
}
}
int k = int(sqrt(b0));
if (k * k == b0 && b0 % k == 0) {
int x = (b1 / b0) * k;
if (gcd(x, b0) == k && gcd(x, a0) == a1) cnt ++;
}
printf("%d\n", cnt);
}
return 0;
}
Sol2
证明Sol1中的推论不难
设
a = p_{1}^{a_1} * p_{2}^{a_2} * \cdots * p_{n}^{a_n}
b = p_1^{b_1} * p_2^{b_2}* \cdots *p_n^{b_n}
由此推出
a*b = p_1^{a_1 + b_1} * p_2^{a_2 + b_2} * \cdots * p_n^{a_n + b_n}
=gcd(a,b) * lcm(a,b)
那么对于这道题我们预处理[1,\sqrt{b_0}]的质数表
然后对于表中每个质数p,我们设在唯一分解下,x, a_0, a_1, b_0, b_1对于质数p分解后p的次数分别是:c, c_1, c_2, c_3, c_4
那么min(c,c_1) = c_2与max(c,c_3) = c_4之间会有限制关系
因为我实在是打烦躁了,所以不列举了
上代码吧
#include
using namespace std;
const int SIZE = 5e4 + 5;
int T, a0, a1, b0, b1, cnt, ans;
int v[SIZE], prime[SIZE];
inline int read()
{
char ch = getchar();
int f = 1, x = 0;
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
return x * f;
}
inline void getPrime()
{
for (int i = 2; i <= 50000; ++ i) {
if (!v[i]) {
prime[++ cnt] = i;
v[i] = i;
}
for (int j = 1; j <= cnt; ++ j) {
if (prime[j] > v[i] || prime[j] > 50000 / i) { break; }
v[i * prime[j]] = prime[j];
}
}
}
inline void solve(int p)
{
int c1 = 0, c2 = 0, c3 = 0, c4 = 0;
while (a0 % p == 0) { a0 /= p; ++ c1; }
while (a1 % p == 0) { a1 /= p; ++ c2; }
while (b0 % p == 0) { b0 /= p; ++ c3; }
while (b1 % p == 0) { b1 /= p; ++ c4; }
if (c2 > c1 || c2 > c4) ans = 0;
if (c1 > c2 && c4 > c3 && c4 > c2) ans = 0;
if ((c1 > c2 || c4 > c3) && c4 >= c2) ans *= 1;
if (c1 == c2 && c3 == c4) ans *= (c4 - c2 + 1);
}
int main()
{
T = read();
getPrime();
while (T --) {
a0 = read(), a1 = read(), b0 = read(), b1 = read();
ans = 1;
for (int i = 1; i <= cnt && ans; ++ i) {
if (b1 % prime[i] == 0) { solve(prime[i]); }
}
if (b1 > 1) solve(b1);
printf("%d\n", ans);
}
return 0;
}
Summary
这道题确实经典,还是蛮不错的
其实Sol2就是由Sol1推论证明的一个关键推出来的
Comments | 1 条评论
orz 踢哦恩歪