2024上海大学生程序设计竞赛I-六元组计数&原根知识详解

以前基本没有了解原根相关的一块内容，最近正好碰到了这个题，于是写一篇博客记录一下。

这道题的总体思路就是比较明显，就是先算出 a p = x a^p=x ap=x对于每个 x x x的解的个数，然后NTT算一下即可。

先来讲一下怎么求欧拉函数 ϕ ( x ) \phi (x) ϕ(x)，即1到 x − 1 x-1 x−1中与 x x x互素的数的个数，我们一般在线性筛里面通过递推来求出这个函数。也就是我们要找出 ϕ ( i ∗ p [ j ] ) \phi(i*p[j]) ϕ(i∗p[j])和 ϕ ( i ) , ϕ ( p [ j ] ) , i , p [ j ] \phi (i),\phi(p[j]),i,p[j] ϕ(i),ϕ(p[j]),i,p[j]之间的关系。我们把与 ϕ ( i ) \phi(i) ϕ(i)所代表的集合写在一行里面，然后第二行写上前一行的数加上 i i i，一直写 p [ j ] p[j] p[j]行。

现在举两个例子。

例1：

i%p[j]!=0
p[j]=3,i=8//虽然实际不会出现这种，但是对于证明来讲问题不大
1  3  5  7
9  11 13 15
17 19 21 23
然后phi[24]表示的集合为
1       5   7
   11  13
17 19       23  

例2：

i%p[j]==0
p[j]=2,i=10
1  3  7  9
11 13 17 19
phi[i*p[j]]=8

在例1中，因为 i m o d    p [ j ] ≠ 0 i \mod p[j] \ne 0 imodp[j]=0，也就是 ϕ ( i ) \phi(i) ϕ(i)所表示的集合中存在 p [ j ] p[j] p[j]的倍数。然后你可以发现，每一列里面恰好就有一个是 p [ j ] p[j] p[j]的倍数，我们不妨设某一列第一个数为 x x x，且 y = x m o d    p [ j ] y=x\mod p[j] y=xmodp[j]，那么因为 p [ j ] p[j] p[j]为质数，所以 y m o d    p [ j ] , y + i m o d    p [ j ] , y + 2 i m o d    p [ j ] , . . . , y + ( p [ j ] − 1 ) i m o d    p [ j ] y\mod p[j],y+i\mod p[j],y+2i\mod p[j],...,y+(p[j]-1)i\mod p[j] ymodp[j],y+imodp[j],y+2imodp[j],...,y+(p[j]−1)imodp[j]中 0 , 1 , . . . , p [ j ] − 1 0,1,...,p[j]-1 0,1,...,p[j]−1恰好每个一个，因此可以知道 p h i [ i ∗ p [ j ] ] = p h i [ i ] ∗ ( p [ j ] − 1 ) ( i m o d    p [ j ] ≠ 0 ) phi[i*p[j]]=phi[i]*(p[j]-1)(i \mod p[j] \ne 0) phi[i∗p[j]]=phi[i]∗(p[j]−1)(imodp[j]=0)。

在例2中，因为 i m o d    p [ j ] = 0 i\mod p[j] =0 imodp[j]=0，因此 ϕ ( i ) \phi(i) ϕ(i)所表示的集合里面没有 p [ j ] p[j] p[j]的倍数，因此第一行里面没有被删掉的，因为相邻两行之间的差都是 p [ j ] p[j] p[j]的倍数，所以不会有任何的数为 p [ j ] p[j] p[j]的倍数。

然后就是原根部分的知识。

如果 x x x是模 P P P意义下的原根，那么 1 , 2 , . . . , P − 1 1,2,...,P-1 1,2,...,P−1中每个数都能写成 x t ( 0