「P10394 接连不断！」题解

P10394 接连不断！

题意

有 $m+1$ 个无向图，编号为 $0\sim m$。每个图的点集都是 $V$，点集 $V$ 包含 $n$ 个点，编号为 $0\sim n-1$。起初所有的图都没有边存在。

在编号为 $x$ 的图中，对于所有在 $[0, n - 1]$ 中的编号 $i$，将编号为 $i$ 的点与编号为 $(i\cdot x)\bmod n$ 的点连一条无向边。

求这 $m+1$ 个图中有多少个图是连通的。

【数据规模与约定】

• 对于 $100\%$ 的数据，保证 $1\le T\le 5,1\le n,m\le 10^{14}$。

题解

图论

观察题目，首先我们发现，在所有图中，对编号为 $0$ 的点，$(0\cdot x)\bmod n = 0$，因此 $0$ 号节点必然存在一个自环。要让剩下的 $n-1$ 条边联通 $n$ 个节点，其必然构成一棵树。

不妨这样考虑：在编号为 $x$ 的图中，每个节点 $i$ 都会向 $(i\cdot x)\bmod n$ 连一条有向边。

显然，如果该图构成树（该图联通时），除了 $0$ 号节点外，$(i\cdot x)\bmod n$ 节点即为 $i$ 节点的父节点。而 $0$ 号节点是树的根节点。

由树的性质我们可以知道，从任意一个节点顺着有向边向上找父节点，最终会到达根节点。

对 $i$ 节点，

• 向上跳一次：$(i\cdot x)\bmod n$
• 向上跳两次：$(((i\cdot x)\bmod n)\cdot x)\bmod n = (i\cdot x^2) \bmod n$
• ...
• 向上跳 $k$ 次：$(i\cdot x^k) \bmod n$

最终会到达根节点，我们用数学语言表示它：

$$ \exists \ k \in \mathbb{N}^+, \ (i\cdot x^k) \equiv 0 \pmod n $$

换句话说，编号为 $x$ 的图联通的充要条件就为：

$$ \forall \ i \in [1,n] \\ \exists \ k \in \mathbb{N}^+, \ (i\cdot x^k) \equiv 0 \pmod n $$

数论

当 $x=0$ 时图显然联通（全都连到根节点上了），我们考虑 $x\in [1, m]$ 的情况。
注意到，命题可直接转化为 $\exists \ k\in \mathbb{N}^+, \ x^k \equiv 0 \pmod n$。

为什么？考虑 $i=1$，则 $\exists \ k\in \mathbb{N}^+, \ x^k \equiv 0 \pmod n$ 具有必要性，
若 $\exists \ k\in \mathbb{N}^+, \ x^k \equiv 0 \pmod n$ 成立，上述条件显然成立，具有充分性。

为了更好地表示 $x$ 与 $n$ 的关系，我们对 $x$、$x^k$ 和 $n$ 进行质因数分解，得到分解结果：

• $x = p_1^{a_1} \cdot p_2^{a_2} \cdot p_3^{a_3} \cdots$
• $x^k = p_1^{ka_1} \cdot p_2^{ka_2} \cdot p_3^{ka_3} \cdots$
• $n = q_1^{b_1} \cdot q_2^{b_2} \cdot q_3^{b_3} \cdots$

由于 $x^k \equiv 0 \pmod{n}$，那么对于 $n$ 的每个质因数 $q_i$，$x^k$ 必须包含这个质因数，且 $ka_i \geq b_i$。又由于 $k\in \mathbb{N}^+$，我们只需要保证 $a_i \ne 0 $ （即 $x$ 有这个质因数 $q_i$）即可。

因此我们将题意进一步转化为：
$x\in [1, m]$ 中有多少 $x$ 满足 $x$ 包含 $n$ 所有质因数（当然，不要忘了加上 $x=0$ 的情况）

记 $t$ 表示 $n$ 所有质因数去重后的乘积，对于一个满足条件的 $x$，显然有 $\frac{x}{t} = c, \ (c \in \mathbb{N}^+)$，即 $c \cdot t = x, \ (c \in \mathbb{N}^+)$。

由于 $x \leq m$，则 $c \cdot t \leq m, \ (c \in \mathbb{N}^+)$，也就是 $c \leq \frac{m}{t}, \ (c \in \mathbb{N}^+)$，故可以得到符合题意的 $x$ 的个数为:

$$ \lfloor \frac{m}{t} \rfloor + 1 $$

(最后 $+1$ 是因为要加上 $x=0$ 的情况)

Q.E.D.

CODE

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while(T--){
        ll n, m;
        cin >> n >> m;
        ll t = 1;
        for(ll i=2;i*i<=n;i++){
            if(n%i==0) {
                while(n%i==0) n /= i;
                t *= i;
            }
        }
        if(n!=1){ // n是素数
            t *= n;
        }
        cout << m/t + 1 << "\n";
    }
    return 0;
}