P10084 [GDKOI2024 提高组] 计算 题解

· · 题解

先考虑怎么求 F(x,a,b)，易得 \gcd(x^a-1,x^b-1)=x^{\gcd(a,b)}-1。

所以 L=m^{\gcd(a,b)}+1,R=m^{\gcd(c,d)}，然后发现 [L,R] 中的数模 m 后每种余数出现次数相同，下面记其为 n=\frac{R-L}{m}。

考虑用生成函数做，易得答案为：

\sum_{i=0}^{\infty}[m\mid i][x^i]\prod_{j=0}^{m-1}(x^j+1)^n

套一下单位根反演的式子 \sum_{k=0}^{\infty}[n\mid k]f_k=\frac{1}{m}\sum_{i=0}^{m-1}f(\omega_m^i) 得：

\frac{1}{m}\sum_{i=0}^{m-1}\prod_{j=0}^{m-1}(\omega_m^{ij}+1)^n

注意到 \omega_m^m=1。设 d=\gcd(m,i)，那么 ij \operatorname{mod} m 对于所有 j=0,1,\dots,m-1 恰好取遍了 \{0,d,2d,\dots,m-d\} 中的每个数各 d 次，于是枚举 d，式子转化为：

\begin{aligned} &\frac{1}{m}\sum_{k|m}\varphi(\frac{m}{k})\prod_{j=0}^{m/k-1}(\omega_m^{kj}+1)^{nk}\\ =&\frac{1}{m}\sum_{k|m}\varphi(\frac{m}{k})\left(\prod_{j=0}^{m/k-1}(\omega_{m/k}^{j}+1)\right)^{nk} \end{aligned}

考虑右边这个括号里的东西怎么求，由因式分解知识可得 x^k-1=\prod_{i=0}^{k-1}(x-\omega_k^i)，带入 x=-1 就出来了，于是式子转化为：

\frac{1}{m}\sum_{k|m}\varphi(\frac{m}{k})2^{nk}[2\nmid \frac{m}{k}]

然后直接 \mathcal O(\sqrt m) 枚举 m 的每个因子做就好了，可以通过此题。

参考代码：

#include<bits/stdc++.h>
#define ll long long
#define mxn 10000003
#define md 998244353
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
ll power(ll x,int y){
    ll ans=1;
    for(;y;y>>=1){
        if(y&1)ans=ans*x%md;
        x=x*x%md;
    }
    return ans;
}
ll power1(ll x,int y){
    ll ans=1;
    for(;y;y>>=1){
        if(y&1)ans*=x;
        x*=x;
    }
    return ans;
}
inline int gcd(int x,int y){
    while(y^=x^=y^=x%=y);
    return x;
}
int t,m,a,b,c,d,tot,p[mxn],f[mxn],phi[mxn];
ll l,r,n,g,ans;
void init(int n){
    phi[1]=1;
    rep(i,2,n){
        if(!f[i])f[i]=p[++tot]=i,phi[i]=i-1;
        rep(j,1,tot){
            if(p[j]>f[i]||p[j]>n/i)break;
            f[p[j]*i]=p[j];
            phi[p[j]*i]=i%p[j]?phi[i]*(p[j]-1):phi[i]*p[j];
        }
    }
}
signed main(){
    init(1e7);
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d%d%d",&m,&a,&b,&c,&d);
        l=a==0||b==0?0:power1(m,gcd(a,b));
        r=power1(m,gcd(c,d));
        n=(r-l)/m;
        ans=0;
        g=power(2,n%(md-1));
        rep(k,1,sqrt(m))if(m%k==0){
            if(k&1)ans=(ans+phi[k]*power(g,m/k))%md;
            if(m/k!=k){
                if((m/k)&1)ans=(ans+phi[m/k]*power(g,k))%md;
            }
        }
        printf("%lld\n",(ans*power(m,md-2)%md+md)%md);
    }
    return 0;
}