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

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

Part1:建图

模(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)) imes log p)) 的时间内完成(.)

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

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

模(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^2log p))实际情况下也能过(.)

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

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

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

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

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

那么这个问题怎么解决呢(?)

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

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

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

可以直接(O(nlog p imes K))暴力解决(,)其中(K)为(phi(p))的质因数个数(.)

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

首先用(O(nlog p imes K))的复杂度算出这(O(n))个数的指标(,)

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

复杂度(O(nlog p imes K + d(phi(p)) imes K))