专栏文章

题解：AT_agc063_d [AGC063D] Many CRT

ddiqiuyi奶龙
AT_agc063_d题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minll7nm
此快照首次捕获于
2025/12/02 04:24
3 个月前
此快照最后确认于
2025/12/02 04:24
3 个月前
查看原文
完全不会做，但是这题可以线性。
认为 n,a,b,c,dn,a,b,c,d 同阶。
x≡a+kb(modc+kd)x\equiv a+kb\pmod {c+kd} 这个式子右边不是定值，不太好合并。但是注意到两边同乘 dd 后会变成 dx≡ad−bc(modc+kd)dx\equiv ad-bc\pmod {c+kd}，这样就可以把模数合并了。但是要注意 dx≡ad−bc(modc+kd)dx\equiv ad-bc\pmod {c+kd} 只在 gcd⁡(c,d)=1\gcd(c,d)=1 时可以变回原式，所以先假装 gcd⁡(c,d)=1\gcd(c,d)=1。
记 M=lcmk=0n−1(c+kd)M=\text{lcm}_{k=0}^{n-1}(c+kd)，那么有 dx≡ad−bc(modM)dx\equiv ad-bc\pmod M，即存在一个 yy 满足 x=My+(ad−bc) mod Mdx=\dfrac{My+(ad-bc)\bmod M}d，那么限制就是 My+(ad−bc) mod M≥0,d∣My+(ad−bc) mod MMy+(ad-bc)\bmod M\ge 0,d\mid My+(ad-bc)\bmod M。
显然 yy 是 O(d)O(d) 的，所以我们只需要求出 M mod dM\bmod d 和 M mod 998244353M\bmod \text{998244353}。
求 nn 个数的 lcm\text{lcm} 并不容易，而分解 nn 个数的质因数的复杂度也不能承受，所以考虑找性质。注意到 gcd⁡(c+id,c+jd)∣(j−i)d(i<j)\gcd(c+id,c+jd)\mid (j-i)d(i<j)，又 gcd⁡(c+id,d)=1\gcd(c+id,d)=1，有 gcd⁡(c+id,c+jd)∣j−i\gcd(c+id,c+jd)\mid j-i。所以只有 <n<n 的质因数可能会重复出现。对于质数 pp，若 p∣dp\mid d，显然不会出现在 MM 中；若 p∤dp\nmid d，则可以求出 0≤x<p0\le x<p，满足 p∣c+kdp\mid c+kd 当且仅当 k≡x(modp)k\equiv x\pmod p。枚举所有的 pkp^k，从而算出 pp 在 ∏(c+id)\prod (c+id) 中的出现次数和以及出现的最高次幂即可算出它的贡献。由于要求逆元，这里是 O(n)O(n) 的。
剩下的部分就比较容易了，枚举 yy 后直接判断即可，但是要特别注意这两个限制是否判断对了（尤其是 y=0y=0 的时候）。
接下来是 gcd⁡(c,d)>1\gcd(c,d)>1 的情况。因为 x≡a(modc),x≡a+b(modc+d)x\equiv a\pmod c,x\equiv a+b\pmod {c+d}，所以有解要求 gcd⁡(c,d)∣b\gcd(c,d)\mid b，那么直接把 gcd⁡(c,d)\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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...