自动搬运

查看原文

来自洛谷，原作者为

	lzy20091001 花开堪折直须折，莫待无花空折枝。

搬运于2025-08-24 22:57:33，当前版本为作者最后更新于2024-05-02 21:07:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

洛谷 P10394 接连不断！

分析

编号为 $0$ 的图显然满足题意。

在编号为 $x \ (x \ne 0)$ 的图中，每一个点都只会连出一条边，而编号为 $0$ 的点总是和自己连边，这意味着有效的边至多有 $n - 1$ 条。而这张图要求连通，那么这张图一定是一棵树，$n - 1$ 条边都是有效的，具体地，没有重边和环。

我们指定 $(i \cdot x) \bmod n$ 是 $i$ 的父亲，那么这棵树就会呈现以编号为 $0$ 的点为根的形态。这是因为除编号为 $0$ 的点都没有自环，向父亲回溯时只有走到编号为 $0$ 的点才会停止。在这个形态下观察这棵树，指定根结点 $0$ 在第 $0$ 层，则对于第 $k$ 层的点 $i$，有 $i \cdot x ^ k \equiv 0 \pmod n$。

因此问题转化为对于 $x \in [1, m]$，有哪些 $x$ 满足对于任意 $i \in [1, n - 1]$ 都可以找到一个最小的 $k$ 使得 $i \cdot x ^ k \equiv 0 \pmod n$。

结论是当且仅当 $x$ 是 $n$ 质因数的乘积的倍数时满足要求。下面给出证明。

由唯一分解定理，设 $n = \prod _ {i = 1} ^ {s} p _ i ^ {r _ i}$（其中 $p$ 为质数），记 $t = \prod _ {i = 1} ^ {s} p _ i$，不妨设 $x = c \cdot t$。

• 必要性：一定存在 $i \in [1, n - 1]$ 且 $i \perp n$（如 $i = n - 1$）。若 $x \ne c \cdot t$，则 $n$ 有 $i \cdot x ^ k$ 所没有的质因子，所以 $i \cdot x ^ k \equiv 0 \pmod n$ 总不成立。
• 充分性：$x = c \cdot t$ 时，$k = \max _ {i = 1} ^ {s} \{r _ i \}$ 时显然满足，不断枚举 $k \gets k - 1$ 直到 $i \cdot x ^ {k - 1} \equiv 0 \pmod n$ 不成立即可找到最小的 $k$。

$[1, m]$ 中有 $\lfloor \dfrac{m}{t} \rfloor$ 个整数是 $t$ 的倍数，再加上编号为 $0$ 的图，所以最终的答案即为 $\lfloor \dfrac{m}{t} \rfloor + 1$，其中 $t$ 为 $n$ 所有质因数的乘积。

将 $n$ 分解质因数的方法可以参考 OI Wiki，本题中 $O (\sqrt n)$ 的朴素方法即可通过，这样最终的时间复杂度为 $O(T \sqrt n)$。

实现

#include <iostream>

long long f(long long n) // n 所有质因数的乘积
{
    long long res = 1;
    for (int i = 2; 1ll * i * i <= n; i++)
    {
        if (n % i == 0)
            res *= i;
        while (n % i == 0)
            n /= i;
    }
    if (n != 1)
        res *= n;
    return res;
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int t;
    std::cin >> t;
    while (t--)
    {
        long long n, m;
        std::cin >> n >> m;
        std::cout << m / f(n) + 1 << "\n";
    }

    return 0;
}