CodeForces – 1089F – Fractions

题意

给定正整数 $n\leq 10^9$,需要构造出不超过 $10^5$ 个真分数,满足:

  • $\frac{a_1}{b_1}+\frac{a_2}{b_2}+\cdots+\frac{a_t}{b_t}+\frac{1}{n}=1$.
  • 对每个分数,$b_i<n$ 且 $b_i\mid n$.

若无解,输出 $-1$,否则给出一组可行解。

分析

先将 $n$ 质因数分解,分下列情况讨论。

首先考虑特殊情况。$n = p^m$,其中 $p$ 是质数。

要选一个因数作为分母,发现 $n$ 的任意一个因数 $b$,都一定是 $p^a$ 的形式。

因为分母为 $1$ 时不合题意,所以在 $1$ 之外,我们任选 $n$ 的两个因子,不妨设为 $c, d$,一定有 $\gcd(c, d)\neq 1$.

又因为 $\gcd(n-1, n)=1$,而 $\gcd(c, d)\neq 1$。以 $c, d$ 作为分母,一定不合法。

也就是说,当 $n=p^m$ 时,不存在合法解

对于其他情况,$n$ 一定可以被表示为两个互质的数的乘积。一种构造方法是:

将 $n$ 质因数分解,不妨 $n=p_1^{m_1}p_2^{m2}\cdots p_t^{m_t}$,令 $x=p_1^{m_1}$,$y=p_2^{m_2}\cdots p_t^{m_t}$,显然 $xy=n$ 且 $\gcd(x, y)=1$.

为了方便,我们钦定 $x\leq y$。如果按照上面的方法得到的 $x>y$,交换 $x, y$ 即可。

当 $k=2$ 时,设题目所求的 $\frac{a_1}{b_1}=\frac{c}{x}$,$\frac{a_2}{b_2}=\frac{d}{y}$.

我们需要求出一组 $(c, d)$ 满足 $\frac{c}{x}+\frac{d}{y}=1-\frac{1}{n}\Rightarrow \frac{c\cdot y+d\cdot x}{xy}=\frac{n-1}{n}$.

因为 $xy=n$,这等价于满足:
$$
c\cdot y+d\cdot x=n-1
$$
继续整理,把 $c\cdot y$ 移到右侧,得到:
$$
d=\frac{n-1-cy}{x}
$$
注意 $c, d\in \Bbb{Z}^+$。

先不考虑 $d$ 的正负性。由于 $x\mid n$,有:
$$
d\in \Bbb{Z}\Rightarrow x\mid(n-1-c\cdot y)\Rightarrow x\mid (1+c\cdot y)
$$
想要找到满足 $x\mid (1+c\cdot y)$ 的 $c$,考虑直接枚举

注意到 $\gcd(x, y)=1$。当 $c$ 取 $1, 2, \cdots x-1$ 时,都有 $x\nmid (c\cdot y)$,所以 $c\cdot y$ 的取值构成 $\operatorname{mod} x$ 的完全剩余系。

也就是说,当 $c$ 遍历 $1\sim x-1$ 时,$c\cdot y\bmod x$ 的取值两两不同,也恰好完全覆盖了 $1\sim x-1$.

因此,一定存在 $c\in[1, x-1]$ 满足 $x\mid (c\cdot y+1)$.

再看 $d$ 的正负性。由于 $1+c \cdot y \leq 1+(x-1) \cdot y=1+xy-y=n-(y-1) < n$,所以 $n-(1\cdot y)>0$.

因此,一定有 $d=\frac{n-1-cy}{x}>0$.

综上

我们先按照 $x=p_1^{m_1}$,$y=p_2^{m_2}\cdots p_t^{m_t}$ 的方法找到 $(x, y)$.

之后,在范围 $1\sim x-1$ 中枚举 $c$,找到满足 $x\mid(c\cdot y+1)$ 的 $c$,计算出 $d=\frac{n-1-cy}{x}$。

$(\frac{c}{x}, \frac{d}{y})$ 即为满足题意的两个分数。

时间复杂度

找到 $(x, y)$ 的部分,需要对 $x$ 分解质因数,时间复杂度为 $\mathcal{O}(\sqrt{n})$.

枚举 $c$ 的部分,因为我们钦定了 $x\leq y$,把 $[1, x-1]$ 看作 $x$ 个数,那么:
$$
x=\sqrt{x\cdot x}\leq \sqrt{x\cdot y}=\sqrt{n}
$$
所以总时间复杂度是 $\mathcal{O}(\sqrt{n})$ 的。

代码

int n;
vector<int> fac;
int main() {
    scanf("%d", &n);
    int p1 = -1;
    for(int i = 2; i * i <= n; i++) {
        if(n % i == 0) {p1 = i; break;}
    }
    if(p1 == -1) p1 = n;
    int x = p1, y = n / p1;
    while(y % p1 == 0) y /= p1, x *= p1;
    if(y == 1) {
        cout << "NO" << endl;
        return 0;
    }
    int ansc, ansd;
    for(int c = 1; c <= x - 1; c++) {
        if((c * y + 1) % x == 0) {
            ansc = c; ansd = (n - 1 - c * y) / x;
            break;
        }
    }
    cout << "YES\n2\n" << ansc << " " << x << "\n" << ansd << " " << y << endl;
    return 0;
}
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇
window.pjaxLoaded = function(){ } window.pjaxLoaded();