题解：AT_agc063_d [AGC063D] Many CRT
diqiuyi
·
·
题解
完全不会做，但是这题可以线性。
认为 n,a,b,c,d 同阶。
记 $M=\text{lcm}_{k=0}^{n-1}(c+kd)$，那么有 $dx\equiv ad-bc\pmod M$，即存在一个 $y$ 满足 $x=\dfrac{My+(ad-bc)\bmod M}d$，那么限制就是 $My+(ad-bc)\bmod M\ge 0,d\mid My+(ad-bc)\bmod M$。
显然 $y$ 是 $O(d)$ 的，所以我们只需要求出 $M\bmod d$ 和 $M\bmod \text{998244353}$。
求 $n$ 个数的 $\text{lcm}$ 并不容易，而分解 $n$ 个数的质因数的复杂度也不能承受，所以考虑找性质。注意到 $\gcd(c+id,c+jd)\mid (j-i)d(i<j)$，又 $\gcd(c+id,d)=1$，有 $\gcd(c+id,c+jd)\mid j-i$。所以只有 $<n$ 的质因数可能会重复出现。对于质数 $p$，若 $p\mid d$，显然不会出现在 $M$ 中；若 $p\nmid d$，则可以求出 $0\le x<p$，满足 $p\mid c+kd$ 当且仅当 $k\equiv x\pmod p$。枚举所有的 $p^k$，从而算出 $p$ 在 $\prod (c+id)$ 中的出现次数和以及出现的最高次幂即可算出它的贡献。由于要求逆元，这里是 $O(n)$ 的。
剩下的部分就比较容易了，枚举 $y$ 后直接判断即可，但是要特别注意这两个限制是否判断对了（尤其是 $y=0$ 的时候）。
接下来是 $\gcd(c,d)>1$ 的情况。因为 $x\equiv a\pmod c,x\equiv a+b\pmod {c+d}$，所以有解要求 $\gcd(c,d)\mid b$，那么直接把 $\gcd(c,d)$ 除掉即可。
```cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=998244353;
const ll inf=1e12;
int n,a,b,c,d,prime[114514],cnt;
ll w[1000005];
bitset<1000005> vis;
int Pow(int x,int y,int p){
int res=1;
for(;y;y>>=1,x=1ll*x*x%p)
if(y&1)
res=1ll*res*x%p;
return res;
}
void exgcd(ll &x,ll &y,ll a,ll b){
if(!b){
x=1,y=0;
return ;
}
exgcd(y,x,b,a%b),y-=a/b*x;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>a>>b>>c>>d;
int g=__gcd(c,d);
if(b%g) return cout<<"-1\n",0;
int aa=a%g;a/=g;
b/=g,c/=g,d/=g;
int m=1,pr=1;
ll num=1;
for(int i=0;i<n;i++) w[i]=c+1ll*i*d;
for(int i=0;i<n&&num<=inf;i++) num=min((__int128)inf+1,(__int128)num*w[i]/__gcd(num,w[i]));
for(int i=2;i<=n;i++){
if(!vis[i]){
prime[++cnt]=i;
if(d%i){
int sm=0,mx=0;
for(ll p=i,j=1;;p*=i,j++){
ll x,y;
exgcd(x,y,d,p);
x=-1ll*x*c%p,x=(x+p)%p;
if(x>=n) break;
sm+=(n-x-1)/p+1,mx=j;
}
sm-=mx;
ll x,y;
exgcd(x,y,d,i),y=(y+d)%d;
// cout<<1ll*i*y%d<<endl;
pr=1ll*pr*Pow(Pow(i,mod-2,mod),sm,mod)%mod,m=1ll*m*Pow(y,sm,d)%d;
}
}
for(int j=1;prime[j]*i<=n;j++){
vis[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
for(int i=0;i<n;i++) m=1ll*m*w[i]%d,pr=1ll*pr*(w[i]%mod)%mod;
ll dw=1ll*a*d-1ll*b*c;
if(num<=inf) dw=(dw%num+num)%num;
for(int k=0;;k++)
if((1ll*k*m+dw)%d==0&&k*num+dw>=0){
int x=(1ll*k*pr+dw)%mod*Pow(d,mod-2,mod)%mod;
cout<<((1ll*x*g+aa)%mod+mod)%mod<<'\n';
return 0;
}
return 0;
}
```