自动搬运

查看原文

来自洛谷，原作者为

	Tangninghaha “I have nothing to offer but blood, toil, tears and sweat.”

搬运于2025-08-24 22:54:30，当前版本为作者最后更新于2024-01-20 16:07:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

看不清公式可以放大。

题意简单转化

首先有 $\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}$。

我们知道展开这个多项式，就相当于在每一个括号内选取一项相乘。

$(1+x^{i})$，如果选择1，乘积的指数不变，表示子集中没有 $i$。如果选择 $x^{i}$，乘积的指数增加了 $i$，表示子集中有 $i$。那么如果展开后有一项 $c_{i}x^{i}$，其中 $c_{i}$ 是系数，那么 $c_{i}$ 就表示子集和为 $i$ 的方案数。

因为 $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 个，可以通过本题。

代码：

#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);
  }
}