「题解」P10394 接连不断！

· · 题解

题目&题意

Link

即求出对于所给图集中全连通部分的数量。

分析&思路

第一眼，不免认为是道图论题，但观数据 1\le n,m \le10^{14}，就是 O\left(n\right) 也得炸，所以一定有所规律于其中。

从全连通入手，则有效边数量为 n-1 条，即 1 棵树，其中 n-1 条边都不存在重边和环。

如果你观察力不错，可以很容易地发现，在第图 x 中，点 i\in \left[0,n-1\right] 会与点 \left(i\cdot x\right)\!\!\!\mod n 相连，指定 \left(i\cdot x\right)\!\!\!\mod n 为 i 的父亲，\because 除 0 外所以点都不存在自环，\therefore 对于向父亲节点回溯的只有到达 0 后才会停止，即当指定 0 为根且位于深度 0，有 i\cdot x^k \equiv 0\left(\!\!\!\mod n\right)。

现在问题就转化为对于所有的 x\left(x\in \left[1,m\right]\right)，其中有能令 1 个有效的 k 使所有可能的 i\in\left[0,n-1\right] 满足 的数量。

好拗口 qwq，接下来是更 「qwq」 的证明 qwq。

求证：当且仅当 x 是 n 质因数的乘积的倍数时满足要求如上要求。

证明：

设 n={\textstyle\prod_{i=1}^{s}{p_{i}^{q_i}}}，记 t={\textstyle\prod_{i-1}^{s}{p_i}},设 x=r\cdot t，其中 p 为素数。

则一定存在 i\in\left[0,m-1\right]，若 x\neq r\cdot t，则 n 有 i\cdot x^k 所没有的质因子，则 i\cdot x^k \equiv 0\left(\!\!\!\mod n\right) 总不成立。

当 x=r\cdot t 时，显然满足 k={\textstyle\max_{i=1}^{s}}\left\{q_i\right\} 成立，枚举 k\gets k-1 直至不满足 i\cdot x^k \equiv 0\left(\!\!\!\mod n\right)，即可找到 k_{min}。

可见，其中有 \left\lfloor\frac{m}{t}\right\rfloor 个整数满足，答案即为 \left\lfloor\frac{m}{t}\right\rfloor+1（x=0 情况）。

现在复杂度为 O\left(\sqrt{n}\right)，最多约 5\times 10^7，能过。

AC_Code：

#include <iostream>
#include <algorithm>
#include <queue>
#define int long long
#define maxn 10000010
#define inf 2147483647
using namespace std;
int T,m,n;
//快读快写
inline int read(){
    int x=0,f; char ch=0;
    while(!isdigit(ch)) f=(ch=='-'?-1:1),ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*f;
}
inline void print(int x){
    if(x<0) x=-x,putchar('-');
    if(x>9) print(x/10);
    putchar(x%10+48);
}
inline void write(int x){print(x);putchar('\n');}
int find(int k){//质因子分解
    int tmp=1;
    for(int i=2;i*i<=k;i++){
        if(!(k%i)){
            tmp*=i;
            while(!(k%i)) k/=i;
        }
    }
    return tmp*k;
}
signed main(){
    T=read();
    while(T--){
        n=read(),m=read();
        int k=find(n),ans=(m+1)/k;
        if((m+1)%k)++ans;
        write(ans);
    }
    return 0;//完结撒花
}

结语&思考

写完题解，突然想起兔队的 1 篇题解。

这里会不会也做了什么暗示呢？

急忙去翻出题人，Into_qwq。

Into_qwq，这是不是暗示我们走进数中，从质因子思考呢？

离大谱。