P10084 [GDKOI2024 提高组] 计算题解
Tangninghaha
·
·
题解
看不清公式可以放大。
题意简单转化
首先有 \gcd(x^{a}-1,x^{b}-1)+1=x^{\gcd(a,b)}。
证明：
因为当 a\ge b 时， \gcd(a,b)=\gcd(a-b,b)。
让我们钦定 a\ge b，那么
考虑 \gcd(x^{a}-1,x^{b}-1)=\gcd(x^{a}-x^{b},x^{b}-1)=\gcd(x^{b}(x^{a-b}-1),x^{b}-1)
由于 \gcd(x^{b},x^{b}-1)=1，所以
\gcd(x^{b}(x^{a-b}-1),x^{b}-1)=\gcd(x^{a-b}-1,x^{b}-1)
我们发现指数在更相减损！
直到更相减损结束的时候，即 \gcd(x^{\gcd(a,b)}-1,x^{0}-1) 时，我们得到原式为 x^{\gcd(a,b)}-1。
发现 m\vert L-1 且 m\vert R，将 L,R 都减去 L，原问题相当于 [1,N] 的问题。
这题中有多项式 f(x)=(1+x)(1+x^{2})(1+x^{3})\cdots (1+x^{k})=c_{0}+c_{1}x+c_{2}x^{2}+\cdots+c_{t}x^{t}。
我们知道展开这个多项式，就相当于在每一个括号内选取一项相乘。
因为 $x$ 是任意代入的，所以我们希望代入一些具有优秀性质的 $x$ 来简化我们的运算。
---
引理
$$
[m\vert i]=\frac{1}{m}\sum_{k=0}^{m-1}\omega_{m}^{ik}
$$
证明：
考虑等比数列求和：$S=\frac{\omega_{m}^{im}-1}{\omega_{m}^{i}-1}$，分类讨论：
- 当 $\omega_{m}^{i}\not=1$ 时，可以知道 $i$ 不是 $m$ 的倍数，并且 $\omega_{m}^{im}-1$ 为0。
- 当 $\omega_{m}^{i}=1$ 时，可以知道 $i$ 是 $m$ 的倍数，并且由于分母为0，此时不能使用等比数列求和公式，所以特判。此时 $\omega_{m}^{ik}=1$，因为 $i$ 是 $m$ 的倍数。得到 $\sum_{k=0}^{m-1}\omega_{m}^{ik}=m$，所以除以 $m$ 得到1。
---
将 $m$ 次单位根代入得到 $\sum f(\omega_{m}^{i})$，展开，由引理得到只有 $m\vert i$ 时，系数为 $c_{i}$ 的项的和不为0。而下标为 $m$ 的倍数的数相加得到 $m\times c_{k}$。故答案为
$$
\frac{1}{m}\sum f(\omega_{m}^{i})
$$
问题转化为快速计算该式子。
---
当 $m$ 为奇素数的时候：
考虑：根据单位根的定义，我们可以对 $z^{m}-1$ 在复数域内进行因式分解。得到 $z^{m}-1=(z-\omega_{m}^{0})(z-\omega_{m}^{1})\cdots(z-\omega_{m}^{m-1})$，代入 $z=-1$，进一步得到 $2=(1+\omega_{m}^{1})(1+\omega_{m}^{2})\cdots(1+\omega_{m}^{m})$。又因为 $m$ 是素数，所以 $(1+\omega_{m}^{i})(1+\omega_{m}^{2i})\cdots(1+\omega_{m}^{mi})$ 的指数模 $m$ 组成了一个完全剩余系，其值仍然等于2。
> 当然，如果 $m$ 为偶数的时候，可以得到 $z^{m}=(-1)^{m}=1$，所以该式子等于0。
进一步对其拓展，我们知道 $n$ 是 $m$ 的倍数，那么当 $i>0$ 时， $f(\omega_{m}^{i})=(1+\omega_{m}^{i})(1+\omega_{m}^{2i})\cdots(1+\omega_{m}^{ni})=2^{\frac{n}{m}}$。当 $i=0$ 时，该式等于 $2^{n}$。
所以答案等于 $\frac{1}{m}(2^{n}+(m-1)2^{\frac{n}{m}})$。
---
拓展到 $m$ 一般的情况，考虑假设$(i,m)=p$，1~m分别乘 i 模 m 得到的剩余系，包含 $\frac{m}{p}$ 个数，是由 $p$ 个 模 $\frac{m}{p}$ 的完全剩余系中的数字乘 $p$ 得到的。
那么可以将 $(1+\omega_{m}^{i})(1+\omega_{m}^{2i})\cdots(1+\omega_{m}^{mi})$ 按照模 $m$ 得到的值可以表示为 $[(1+\omega_{m}^{p})(1+\omega_{m}^{2p})\cdots(1+\omega_{m}^{m})]^{p}$。
所以 $f(\omega_{m}^{i})=[(1+\omega_{m}^{p})(1+\omega_{m}^{2p})\cdots(1+\omega_{m}^{m})]^{p\times \frac{n}{m}}$。
注意到单位根的性质 $\omega_{m}^{p}=\omega_{\frac{m}{p}}^{1}$，所以其实上式中括号内的部分就是 $(1+\omega_{\frac{m}{p}}^{1})(1+\omega_{\frac{m}{p}}^{2})\cdots(1+\omega_{\frac{m}{p}}^{\frac{m}{p}})$。
当 $\frac{m}{p}$ 为偶数的时候，上面的式子为0。当 $\frac{m}{p}$ 为奇数的时候，上面的式子为2。所以 $f(\omega_{m}^{i})=2^{p\times\frac{n}{m}}[2\nmid \frac{m}{p}]$。
所以答案等于 $\frac{1}{m}(2^{n}+\sum_{i=1}^{m-1}2^{\frac{n}{m}\times p}[2\nmid \frac{m}{p}])$。
我们之前特判了 $i=0$ 的情况，其实 $i=0$ 和 $i=m$ 是一样的，当 $i=m$ 时，$p=m$，$2^{\frac{n}{m}\times p}[2\nmid \frac{m}{p}])=2^{n}$，所以式子可以简化为：
$$
\frac{1}{m}(\sum_{i=0}^{m-1}2^{\frac{n}{m}\times p}[2\nmid \frac{m}{p}])
$$
直接计算可以获得 85 分。
---
进一步优化，观察到如果 $2\vert \frac{m}{(i,m)}$ 时，$i$ 对答案没有贡献。所以假设 $m=2^{k}\times u$，其中 $u$ 是一个奇数，那么 $i$ 要求满足 $i=2^{k}\times x$。
所以有：
$$
\begin{aligned}
\frac{1}{m}(\sum_{i=0}^{m-1}2^{\frac{n}{m}\times p}[2\nmid \frac{m}{p}])&=\frac{1}{m}(\sum_{i=1}^{u}2^{\frac{n}{2^{k}\times u}\times \gcd(2^{k}\times u,2^{k}\times i)})\\
&=\frac{1}{m}(\sum_{i=1}^{u}2^{\frac{n}{u}\times \gcd(u,i)})
\end{aligned}
$$
考虑到 $\gcd(u,i)$ 为 $u$ 的约数，我们直接枚举 $\gcd(u,i)$，也就是：
$$
\frac{1}{m}(\sum_{d\vert u}2^{\frac{n}{u}\times d}\times \varphi(\frac{u}{d}))
$$
因为 $\gcd(u,i)=d$ 要求 $\gcd(\frac{u}{d},\frac{i}{d})=1$，所以有多少个 $\frac{i}{d}$ 满足 $\gcd(\frac{u}{d},\frac{i}{d})=1$ 就是与 $\frac{u}{d}$ 互质的数字的个数。
由于 $u$ 的特殊性（没有质因子2），所以其约数个数不会太多，1e7 之内大约只有 200 个，可以通过本题。
代码：
```c++
#include<cstdio>
#include<cmath>
using namespace std;
using ll=long long;
const int mod=998244353;
const int M=1e7+5;
ll qpow(ll a,ll b){
ll res=1;
while(b){
if(b&1)res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
ll qpowNoMod(ll a,ll b){
ll res=1;
while(b){
if(b&1)res=res*a;
a=a*a;
b>>=1;
}
return res;
}
int phi[M],pri[M],tot;
bool vis[M];
void init(){
phi[1]=1;
for(int i=2;i<=(int)1e7;++i){
if(!vis[i])phi[i]=i-1,pri[++tot]=i;
for(int j=1;j<=tot;++j){
if(pri[j]*i>1e7)break;
vis[pri[j]*i]=true;
if(i%pri[j]==0){phi[pri[j]*i]=phi[i]*pri[j];break;}
phi[pri[j]*i]=phi[i]*(pri[j]-1);
}
}
}
int gcd(int x,int y){
return y==0?x:gcd(y,x%y);
}
ll F(int m,int x,int y){
if(x==0||y==0)return 0;
return qpowNoMod(m,gcd(x,y));
}
int main(){
init();
int t;
scanf("%d",&t);
while(t--){
int m,a,b,c,d;
scanf("%d%d%d%d%d",&m,&a,&b,&c,&d);
ll l=F(m,a,b)+1,r=F(m,c,d);
ll n=r-l+1;
int u=m;
while(!(u&1))u>>=1;
ll ans=0;
for(int i=1,_i=sqrt(u+0.5);i<=_i;++i){
if(u%i!=0)continue;
ans+=qpow(2,n/u*i)*phi[u/i]%mod;
if(i*i!=u){
int j=u/i;
ans+=qpow(2,n/u*j)*phi[u/j]%mod;
ans%=mod;
}
}
ans*=qpow(m,mod-2);
ans%=mod;
printf("%lld\n",ans);
}
}
```