先考虑怎么求 \(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)\)，带入 \(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;
}