P9796 Fractions

_djc_ · 2023-10-29 08:36:36 · 题解

题目大意

给定一个正整数 n，构造出若干个形如 \frac{a_i} {b_i} 的真分数，使得 \sum_{i=1} ^{k} \frac{a_i} {b_i} =1-\frac {1} {n}，且 b_i 是 n 的因数。

题目分析

由于 b_i 是 n 的因数，所以我们直觉上先把 n 分解一下:

• n = p^m

  在这种情况下，无解。如果 n = p^m，那么 b_i = p^{k_i}(k_i\le m)，并且每个 b_i 都差了 p^x 倍。设最大的一个 b_i 为 t，则通分后的分母为 t，而 t \le n，所以不可能凑成 \frac{n-1}{n}。

• 首先，在这种情况下，如果存在答案，那么 $k$ 一定可以等于 $2$。因为 $b_i | n$，且 $lcm(b_1,b_2,\dots,b_k) = n$，任意选取两个，$lcm(b_x, b_y)|n$，如果 $k>2$，我们可以把它们凑成两个。 $$ \frac{a}{x} + \frac{b}{y} = \frac{n-1}{n} $$ 所以算法的第一步就出来了，$x$ 和 $y$ 任选，只要是 $n$ 的因数且最小公倍数等于 $n$ 就可以了，然后我们再看 $a$ 和 $b$，是否对于任意的 $x$ 和 $y$ 都存在正整数解 $(a,b)$ 且 $a < x,b<y$ 呢？ 先做一个转换，同乘 $xy$： $$ ay+bx=\gcd(x,y)\cdot(n-1) $$ 观察这个式子，在学习拓展欧几里得算法时我们学过，$ax+by$ 一定是 $\gcd(a,b)$ 的倍数，否则无解，由于 $\gcd(x,y)\cdot(n-1)$ 一定是 $\gcd(x,y)$ 的倍数，所以一定是有解的。 还有就是要证明存在一个 $a<x,b<y$ 的情况下的解，设 $a$ 已知，$1\le a < x$，则 $b = \frac{\gcd(x,y)\cdot(n-1)-ay}{x}$。设 $x' = \frac{x}{\gcd(x,y)},y' = \frac{y}{\gcd(x,y)}$，则 $$ b = \frac{(n-1)-ay'}{x'} $$ 若有解，则需要 $b$ 是一个整数，也就是 $$ (n-1)-ay' \equiv 0 \pmod{x'} $$ 我们看 $ay'$，由于 $y'$ 与 $x'$ 互质，所以当 $a\in [0,x-1]$，$ay'\pmod{x'}$ 的值都不相同。 证明：如果有两数相同，$a_1 y' = k_1x'+t,a_2y' = k_2x'+t$，则 $(a_1 - a_2)y' = (k_1 - k_2)x'$，$a_1-a_2$ 需要是 $x'$ 的倍数。 又因为当 $a=0$ 时，$(n-1) \pmod{x'}$ 一定不为 $0$，所以在 $1$ 到 $x-1$ 中一定有一个 $a$ 使得 $(n-1)-ay' \equiv 0 \pmod{x'}$。

代码实现

经过以上分析，代码就可以写出来了。我们先把 n 分解质因数，然后选取 x 和 y，使 \gcd(x,y)=1,x\cdot y = n。然后从 1 到 x-1 枚举 a，每次进行一个判断即可。时间复杂度 O(\sqrt{n})。

最后贴上代码，码风很丑轻点喷。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 100005
inline int read() {
    int x = 0, f = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
    while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}

int vis[maxn], prime[maxn], n, m;

void init() {
    for (int i = 2; i <= 100000; i++) {
        if (!vis[i]) prime[++m] = i, vis[i] = 1;
        for (int j = 1; j <= m && prime[j] * i <= 100000; j++) 
            vis[prime[j] * i] = 1;
    }
}

struct node {
    int v, cnt;
};

vector<node> a;

int ksm(int a, int b) {
    int res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = res * a;
        a = a * a;
    }
    return res;
}

signed main() {
    init();
    n = read();
    for (int i = 1; i <= m; i++) {
        if (n % prime[i] == 0) {
            int tmp = n, cnt = 0;
            while (tmp % prime[i] == 0) {
                cnt++;
                tmp /= prime[i];
            }
            node nw; nw.cnt = cnt, nw.v = prime[i];
            a.push_back(nw);
            break;
        }
    }
    if (a.empty() || ksm(a[0].v, a[0].cnt) == n) {
        puts("NO");
        return 0;
    }
    puts("YES");
    int x = ksm(a[0].v, a[0].cnt);
    int y = n / x, a, b;
    for (a = 1; a < x; a++) {
        if ((n - 1 - a * y) % x == 0) {
            b = (n - 1 - a * y) / x;
            break;
        }
    }
    cout << 2 << endl;
    cout << a << " " << x << endl << b << " " << y;
}