自动搬运

查看原文

来自洛谷，原作者为

	s_r_f 这里是一个只会背板和fst的蒟蒻

搬运于2025-08-24 22:23:26，当前版本为作者最后更新于2020-08-07 12:42:58，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

一个$O(n^2\log)$垃圾做法

考虑建出一张有向图$G,$ 有边$i->j$当且仅当存在一个正整数$m$使得$a_i^m$和$a_j$在模$p$意义下同余$,$然后在图$G$上计算答案$.$

Part1:建图

subtask1:模数为奇质数

模$p$意义下存在原根$,$设为$g.$

那么每个$a_i$都可以表示成$g^{k_i}$

考虑求出一个数$a_i$的指标和$\phi(p)$的$\gcd$的值$k_i(k_i|\phi(p)):$

显然$k_i$为满足$a_i^{\phi(p)/k}$ 模$p$之后为$1$的最大的数$.$

枚举每个质因数$p$求它的次数$,$这个工作就可以在$O(d(\phi(p)) \times \log p)$ 的时间内完成$.$

那么$,$ $i->j$存在当且仅当$k_i|k_j.$

这样就可以$O(1)$ $check$是否存在边$i->j$了

subtask2:模数为奇质数$q$的$t(t>1)$次幂

模$p^k$意义下也存在原根$.$

不难发现我们可以用同样的方法求出所有$k_i,$但是这回一个数可能会是$q$的倍数$,$我们记$a_i$的因数分解中存在的$q$的个数为$m_i.$

这次我们怎么$check$ $i->j$是否可以连边呢$?$

首先如果$m_i=m_j=0,$那么就直接用上一个$subtask$的做法即可$.$

如果有一个$m=0,$而另一个$m ≠ 0,$那么边$i->j$不存在$.$

如果$m_i≠0,m_j≠0,$那么我们可以直接计算出可能使$a_i^z=a_j$的数字$z,z=m_j/m_i,$然后直接快速幂解决$.$

那么就可以$O(\log p)$的复杂度内$check$是否存在边$i->j$了

如果害怕$T$飞的话可以求出原根用光速幂$,$不过$O(n^2\log p)$实际情况下也能过$.$

---

Part2:计算答案

建出图之后$,$我们考虑怎么计算答案$.$

考虑一个$a_i$对答案的贡献$.$

有一个想法是$a_i$在答案中存在的条件为当且仅当没有任何数能够表示出它$,$记这些数的个数为$cnt,$那么$a_i$对答案的贡献就是$2^{cnt}.$

但是这样做忽略了环的情况$,$只能获得$10pts.$

举个例子$,$如果$n=2,$图$G$中存在边$(1,2),(2,1),$如果按照这种算法计算出来的答案就是$2,$而正确答案是$3.$

那么这个问题怎么解决呢$?$

不难发现如果有一个强联通分量$S,$ $S$内部的所有点必然是能两两连边的$,$所以我们可以给一个强联通分量内的点强制一个顺序$,$就可以正确的计算出答案了$.$

代码$:$ 见云剪贴板

---

Bonus:如何解决$n\leq 10^5,p\leq 10^{18}$

首先求出$phi(p),$用$pollard-rho$分解质因数$,$并爆搜出$phi(p)$的因子$.$

对于$\gcd(a_i,p)≠1$的$a_i$的贡献$,$

可以直接$O(n\log p \times K)$暴力解决$,$其中$K$为$phi(p)$的质因数个数$.$

对于$\gcd(a_i,p)=1$的数字$,$

首先用$O(n\log p \times K)$的复杂度算出这$O(n)$个数的指标$,$

然后以这些因子为下标运行狄利克雷前缀和即可$.$

复杂度$O(n\log p \times K + d(phi(p))\times K)$

代码$:$ 见云剪贴板