题解 P6730 【[WC2020] 猜数游戏】

· · 题解

一个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)

代码: 见云剪贴板