LOJ2589.「NOIP2009」Hankson 的趣味题

在复习约数定理和一些推论的时候又发现了这道好题

Link

题意

已知正整数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推论证明的一个关键推出来的