拾起，单位根的记忆

北斗七星 · 2025-11-19 23:36:25 · 个人记录

拾起，单位根的记忆

阶：

定义：

对于 a\in \mathbf{Z} ， m \in \mathbf{N}_+ 且 a\perp m ，满足 a^n \equiv 1\pmod{m} 的最小正整数 n 记为 \delta_m(a)

约定：下列性质均在 a\in \mathbf{Z} ， m \in \mathbf{N}_+ 且 a\perp m 的情况下研究

性质一：

### 性质二： $ a^n\equiv 1 \pmod{m} $ 当且仅当 $ \delta_m(a) \mid n

性质三：

\delta_m(a^k)=\dfrac{\delta_m(a)}{\gcd(\delta_m(a),k)}

性质四：

\dfrac{\operatorname{lcm}(\delta_m(a),\delta_m(b))}{\operatorname{gcd}(\delta_m(a),\delta_m(b))} \mid \delta_m(ab) \mid \operatorname{lcm}(\delta_m(a),\delta_m(b))

更为简单的形式： \delta_m(ab)=\delta_m(a)\delta_m(b) \iff \delta_m(a) \perp \delta_m(b)

性质五：

总存在 c ，满足 \delta_m(c)=\operatorname{lcm}(\delta_m(a),\delta_m(b))

原根：

定义：

若存在 g 满足 \delta_m(g)=\varphi(m) ，则称 g 为模 m 的原根

原根判定定理：

对于 m \ge 3 和 g \perp m ，g 是模 m 的原根当且仅当对于所有 p \mid \varphi(m) ，都有 g^{\frac{\varphi(m)}{p}} \not\equiv1 \pmod m

原根个数定理：

模 m 的原根个数为 \varphi({\varphi{(m)})}

原根存在定理：

模 m 的原根存在当且仅当 m=1,2,4,p^e,2p^e ，其中 p 为奇质数且 e \in \mathbf{N}_+

求原根的算法:

从小到大逐一枚举并判断，直到找到原根

代码：

时间复杂度为 O(n^{\frac{1}{4}}\log n) ，可以找到所有原根

#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
typedef long long ll;
int T,cnt,phi[N],pri[N]; vector<int> factor,ans; bool vis[N];
void init(int n){
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!vis[i]) pri[++cnt]=i,phi[i]=i-1;
        for(int j=1;j<=cnt&&i*pri[j]<=n;j++){
            vis[i*pri[j]]=true;
            if(i%pri[j]==0){
                phi[i*pri[j]]=phi[i]*pri[j];
                break;
            }
            else phi[i*pri[j]]=phi[i]*phi[pri[j]];
        }
    }
}
int qpow(ll a,ll b,int mod){
    ll res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod; b>>=1;
    } return res;
}
void divide(int x){
    for(int i=2;i*i<=x;i++){
        if(x%i==0){
            factor.push_back(i);
            while(x%i==0) x/=i;
        }
    }
    if(x>1) factor.push_back(x);
}
bool exist(int n){
    if(n==2||n==4) return 1;
    if(n%2==0) n/=2;
    for(int i=2;pri[i]<=n;i++){
        if(n%pri[i]==0){
            while(n%pri[i]==0) n/=pri[i];
            return n==1;
        }
    }
    return 0;
}
int main(){
    init(1000000); scanf("%d",&T);
    while(T--){
        int n,d; scanf("%d%d",&n,&d);
        if(!exist(n)){
            puts("0\n");
            continue;
        }
        factor.clear(); ans.clear(); divide(phi[n]);
        int g;
        for(int i=1;;i++){
            bool is=1;
            if(__gcd(i,n)!=1) continue;
            for(int j=0;j<factor.size();j++){
                if(qpow(i,phi[n]/factor[j],n)==1){ is=0; break; }
            }
            if(is){ g=i; break; }
        }
        ll power=1;
        for(int s=1;ans.size()<phi[phi[n]];s++){
            power=power*g%n;
            if(__gcd(phi[n],s)==1) ans.push_back(power);
        }
    }
}

单位根反演：

主要形式： [k\mid n]=\frac{1}{k}\sum\limits_{i=0}^{k-1} \omega_{k}^{in}

在模 m 意义下，取 \omega_k=g^{\frac{\varphi(m)}{k}} ，一般题目的 m 为质数，所以 \omega_k=g^{\frac{m-1}{k}}

多项式中的问题：

对于多项式 f(x) ，求 \sum_i[x^i]f(x)[k\mid i]

用单位根反演： Ans=\sum_i[x^i]f(x)\frac{1}{k}\sum_{j=0}^{k-1}\omega_{k}^{ij}=\frac{1}{k}\sum_{j=0}^{k-1}\sum_i[x^i](\omega_k^{j})^if(x)=\frac{1}{k}\sum_{j=0}^{k-1}f(\omega_k^j)

例题：

约定：保证 k\mid mod-1 且 mod 为质数且存在模 mod 的原根

题目：#6247. 九个太阳

求 \sum_{i=0}^n \binom{n}{i}[k\mid i]

解答：

Ans=\frac{1}{k}\sum_{i=0}^{k-1}f(\omega_k^i) $，其中 $ [x^i]f(x)=\binom{n}{i}
f(x)=\frac{1}{k}\sum_i \binom{n}{i}x^i=(1+x)^n
Ans=\frac{1}{k}\sum_{i=0}^{k-1}(1+\omega_k^i)^n

题目：#6485. LJJ 学二项式定理

求 \sum_{i=0}^n \binom{n}{i} s^i a_{i\% 4}

解答：

枚举 j=i\% 4 ，求 \sum_{i=0}^n \binom{n}{i} s^i a_{j}[4\mid i-j]
Ans=a_j\sum_{i=0}^n\binom{n}{i} s^i\times \frac{1}{4}\sum_{t=0}^{3} \omega_{4}^{ti-tj}
再枚举 t， Ans=\dfrac{a_j}{4\,\omega_4^{tj}}\sum_{i=0}^n \binom{n}{i} (s\times\omega_4^t)^i
后面的式子就是 (s\times\omega_4^t+1)^n

题目：P10664 BZOJ3328 PYXFIB

求 \sum_{i=1}^n [k\mid i]\binom{n}{i}F_i ，其中 F_i 表示斐波那契数列

解答：

值得注意的是，矩阵乘法和单位根反演是兼容的
\begin{bmatrix}F_{i-1}&F_{i-2}\end{bmatrix}\ast \begin{bmatrix}1&1\\1&0\end{bmatrix}=\begin{bmatrix}F_{i}&F_{i-1}\end{bmatrix}
反演可得 Ans=\frac{G}{k} \sum_{i=0}^{k-1} (A\omega_k^i+E)^n，其中 E 为单位矩阵

题目：#5370. 循环序列

求 \sum_{i=0}\binom{k}{ni+x}

解答：

Ans=\frac{1}{n}\sum_{i=0}^{n-1}\omega_n^{-ix}(1+\omega_n^i)^k

题目：P5591 小猪佩奇学数学

求 \sum_{i=0}^n \binom{n}{i}p^i\lfloor \frac{i}{k} \rfloor

解答：

Ans=\sum_{i=0}^{n} \binom{n}{i}p^i \ast \frac{i-i\bmod k}{k}
Ans=\frac{1}{k} \sum_{i=0}^{n} \binom{n}{i}p^i i -\frac{1}{k}\sum_{i=0}^{n} \binom{n}{i}p^i(i\bmod k)
先不管 \dfrac{1}{k} ，将式子拆成左右两边处理
left=\sum_{i=0}^{n} \binom{n}{i}p^i i
left=n\sum_{i=1}^{n} \binom{n-1}{i-1}p^i
left=np\sum_{i=0}^{n-1}\binom{n-1}{i}p^i
left=np(p+1)^{n-1}
right=\sum_{i=0}^{n} \binom{n}{i}p^i(i \bmod k)
right=\sum_{i=0}^{n} \binom{n}{i}p^i\sum_{t=0}^{k-1}[t=i\bmod k]t
[t=i \bmod k]=[k|i-t]=\frac{1}{k}\sum_{j=0}^{k-1} \omega_{k}^{j(i-t)}
right=\frac{1}{k}\sum_{i=0}^{n} \binom{n}{i}p^i\sum_{t=0}^{k-1}t\sum_{j=0}^{k-1} \omega_{k}^{ji}\omega_{k}^{-jt}
不管 \frac{1}{k} ， right \rightarrow \sum_{i=0}^{n} \binom{n}{i}p^i \omega_{k}^{ji}\sum_{t=0}^{k-1}t\sum_{j=0}^{k-1}\omega_{k}^{-jt}
right=(\omega_{k}^{j}p+1)^n\sum_{t=0}^{k-1}t\sum_{j=0}^{k-1}\omega_{k}^{-jt}
枚举 j，不管定值 (\omega_{k}^{j}p+1)^n ， right \rightarrow \sum_{t=0}^{k-1}t\omega_{k}^{-jt}
我们知道， \sum_{i=1}^{n}w^i=\dfrac{w^{n+1}-w}{w-1}
设 F(n,w)=\sum_{i=0}^{n}iw^i=\sum_{i=1}^{n}iw^i
wF(n,w)=\sum_{i=0}^{n}iw^{i+1}=\sum_{i=1}^{n+1}(i-1)w^{i}
(w-1)F(n,w)=nw^{n+1}-\sum_{i=1}^{n}w^i=nw^{n+1}-\dfrac{w^{n+1}-w}{w-1}
right=\dfrac{1}{\omega_{k}^{-j}-1}\begin{pmatrix}(k-1)\omega_{k}^{-jk} -\dfrac{(\omega_{k}^{-jk}-\omega_{k}^{-j})}{\omega_{k}^{-j}-1}\end{pmatrix}
right=\dfrac{1}{\omega_{k}^{-j}-1}\begin{pmatrix}(k-1) -\dfrac{1-\omega_{k}^{-j}}{\omega_{k}^{-j}-1}\end{pmatrix}=\dfrac{k}{\omega_{k}^{-j}-1}
综上， Ans=\dfrac{1}{k} \begin{pmatrix}np(p+1)^{n-1}-\sum_{j=0}^{k-1}\dfrac{(\omega_{k}^{j}p+1)^n}{\omega_{k}^{-j}-1}\end{pmatrix} ，注意讨论 \omega_{k}^{-j}=1 的情况

题目：P10084 [GDKOI2024 提高组] 计算

可转化为： 1,2,\dots,n 的集合，求有多少个子集，满足子集元素和为 k 的倍数，保证 k\mid n

注意：此题不满足约定

解答：

构造生成函数 f(x)=\prod_{i=1}^n(1+x^i) ，则 [x^k]f(x) 就是子集和为 k 的子集个数
不难得到， Ans=\sum_{i} [x^i]f(x)[k\mid i]
Ans=\frac{1}{k}\sum_{i=0}^{k-1} f(\omega_k^i)
考虑求 f(\omega_k^i) ，设 d=\gcd(i,k) ，则 f(\omega_k^i)=f\left(\omega_{\frac{k}{d}}^{\frac{i}{d}}\right)
f\left(\omega_{\frac{k}{d}}^{\frac{i}{d}}\right)=\left(\prod\limits_{i=0}^{\frac{k}{d}-1} \left(1+\omega_{\frac{k}{d}}^i\right) \right)^\frac{nd}{k}
我们知道 x^n-1=\prod_{i=0}^{n-1} (x-\omega_n^i) ，代入 x=-1 ，得 (-1)^n-1=\prod_{i=0}^{n-1} (-1-\omega_n^i)\Rightarrow\prod_{i=0}^{n-1} (1+\omega_n^i)=1-(-1)^n
Ans=\frac{1}{k}\sum_{d\mid k} 2^{\frac{nd}{k}}\sum_{i}[(i,k)=d][2\nmid \frac{k}{d}]
Ans=\frac{1}{k}\sum_{d\mid k} 2^{\frac{nd}{k}}\varphi(\frac{k}{d})[2\nmid \frac{k}{d}]
设 k=u\times 2^m ，其中 2\nmid u ，则 d=v\times 2^m 才满足 [2\nmid \frac{k}{d}]
最终可得 Ans=\frac{1}{k}\sum_{d\mid u} 2^{\frac{nd}{u}}\varphi(\frac{u}{d})

题目：P6800 【模板】Chirp Z-Transform

给定多项式 f(x) ，求 f(c^0),f(c^1),\dots , f(c^m)

解答：

虽然与单位根反演无关

F(c^i)=\sum_{j} a^j c^{ij}
人类智慧： ij=\binom{i+j}{2}-\binom{i}{2}-\binom{j}{2}
F(c^i)=c^{-\binom{i}{2}}\sum_{j} a^jc^{-\binom{j}{2}}\times c^{\binom{i+j}{2}}
记 A_{m-i}= a^ic^{-\binom{i}{2}} ， B_{i}=c^{\binom{i}{2}}

题目：P5293 [HNOI2019] 白兔之舞

矩阵的转移是平凡的，可将问题变为对于每个 t，求 \sum_{i=0}^L \binom{L}{i}[i\equiv t \pmod{k}]W^i

解答：

先定 t， \sum_{i=0}^L \binom{L}{i}[i\equiv t \pmod{k}]W^i=\frac{1}{k}\sum_{i=0}^{k-1} \omega_{k}^{-it} (W\omega_k^i+E)^L
构造多形式 f(x) ，满足 [x^i]f(x)=\frac{1}{k}(W\omega_k^i+E)^L
Ans_t=\sum_{i=0}^{k-1} \omega_{k}^{-it}[x^i]f(x)=f(\omega_{k}^{-t})=f\left((\frac{1}{\omega_k})^t\right)
记 c=\frac{1}{\omega_k} ，即求所有的 f(c^i) ，用上一题的做法即可

题目：TopCoder 11351 TheCowDivOne

\{0,1,\dots,n-1\} $ 中选 $ k $ 个数，和为 $ n $ 的倍数的方案数，模 $ 1e9+7 $，$ k\le1e3 $，$ n\le 1e9

注意：此题不满足约定

解答：

让我们请出二元生成函数

Ans=\sum_{i}[n\mid i][x^i][y^k]\prod_{j=0}^{n-1}(1+x^jy)
Ans=\sum_{i}\frac{1}{n}\sum_{t=0}^{n-1}\omega_n^{ti}[x^i][y^k]\prod_{j=0}^{n-1}(1+x^jy)
Ans=\frac{1}{n}\sum_{t=0}^{n-1}[y^k]\prod_{j=0}^{n-1}(1+\omega_n^{tj}y)
设 d=\gcd(t,n) ， Ans=\frac{1}{n}\sum_{t=0}^{n-1}[y^k]\left(\prod_{i=0}^{\frac{n}{d}-1}\left(1+\omega_{\frac{n}{d}}^iy\right)\right)^d
我们知道 x^n-1=\prod_{i=0}^{n-1} (x-\omega_n^i) ，代入 x=-\frac{1}{y} ，得 (-\frac{1}{y})^n-1=\prod_{i=0}^{n-1} (-\frac{1}{y}-\omega_n^i)\Rightarrow\prod_{i=0}^{n-1} (1+\omega_n^iy)=1-(-y)^n
Ans=\frac{1}{n}\sum_{d\mid n}\varphi(\frac{n}{d})[y^k]\left(1-(-y)^{\frac{n}{d}}\right)^d
Ans=\frac{1}{n}\sum_{d\mid n,k}\varphi(d)[y^{\frac{k}{d}}]\left(1+(-1)^{d+1}y\right)^\frac{n}{d}

题目：HT-054-NOI 优秀的匹配

给定二维数组，问是否有排列 p ，使 k\mid \sum_{i=1}^n a_{i,p_i} 且 \forall \, i,a_{i,p_i}\ne -1

数据范围： 1\le n,k \le 100

解答：

不易想到，行列式的完全展开式里自带枚举排列
构造矩阵 A ，当 a_{i,j}=-1 时， A_{i,j}=0 ，否则 A_{i,j}=x^{a_{i,j}}
若 \exist \,k\mid i,[x^i]det(A)\ne 0 ，则有解
若都等于 0，也可能是正负抵消了，因此将 A_{i,j}=rand()\times x^{a_{i,j}} ，这样可以避免正负抵消
因为加了随机化，事实上，求 Ans=\sum_{k\mid i} [x^i]det(A) 是否为 0 即可
单位根反演， Ans=\frac{1}{k}\sum_{i=0}^{k-1} f(\omega_k^i) ，其中 f(x) 就是 det(A) 对应的多项式
将每个 \omega_k^i 代入算行列式即可

总结：何时用单位根反演：

出现以下情况时，可以考虑：

[k\mid i]
i \equiv x \pmod{k} \Rightarrow [k\mid i-x]
\lfloor \frac{i}{k} \rfloor $，枚举 $ j=i\bmod k $，变为 $ \frac{i-j}{k}
\sum_i f(ki+x) $，可化为 $ \sum_j f(j) [j\equiv x \pmod{k} ]
求和为 k 的倍数的方案数