原题意可能略微有一些复杂，这里给出简述的题意——
给定$g_{i}$和$r_{i}$（其中$1\le i\le 3$），求有多少个整数$t$满足：
$0\le t< \prod_{i=1}^{3}(g_{i}+r_{i})$且$\forall 1\le i\le 3,t\ mod\ (g_{i}+r_{i})<g_{i}$，答案对998244353取模
$1\le g_{i},t_{i}\le 10^{12}$
先来叙述一些关于同余的性质——
性质1：$x\equiv y(mod\ n)$，可推出$x\equiv y(mod\ d)$（其中$d$为$n$的任意约数）
性质2：关于$t$的同余方程$\forall 1\le i\le k,t\equiv x_{i}(mod\ m_{i})$，若其有解$t_{0}$，则$t$为其解当且仅当$t\equiv t_{0}(mod\ M)$，其中$M=lcm(m_{1},m_{2},...,m_{k})$
证明：
充分性——根据性质1，$t\equiv t_{0}(mod\ M)$即可推出$t\equiv t_{0}\equiv x_{i}(mod\ m_{i})$
必要性——$t$为解即有$t\equiv t_{0}(mod\ m_{i})$，也可以写作$m_{i}\mid |t-t_{0}|$，即整除其最小公倍数$M$
定义六元组$(m_{1},x_{1},m_{2},x_{2},m_{3},x_{3})$合法，当且仅当存在$t$使得$\forall 1\le i\le 3,t\equiv x_{i}(mod\ m_{i})$
另外定义$n$中$p$的指数为$ord_{p}(n)$，即$\max_{a\ge 0,p^{a}\mid n}a$
关于$(m_{1},x_{1},m_{2},x_{2},m_{3},x_{3})$合法的一些性质——
（为了方便，记$M=lcm(m_{1},m_{2},m_{3})$，初始的这个六元组写作原六元组）
根据对称性，以下性质都写作修改$m_{1}$，事实上对$m_{2}$或$m_{3}$都是类似的
性质3：对于素数$p$满足$p\mid m_{1}$且$p\not\mid m_{2},m_{3}$，则原六元组合法等价于$(\frac{m_{1}}{P},x_{1},m_{2},x_{2},m_{3},x_{3})$合法（其中$P=p^{ord_{p}(m_{1})}$）
证明：
原六元组若合法，则其$t$也可以作为新的六元组的解（根据性质1），即新的六元组必然合法
若新的六元组合法，对于其解$t_{0}$，考虑构造原六元组的解$t_{1}$
首先$t_{1}$必然要是新六元组的解，即$t_{1}\equiv t_{0}(mod\ \frac{M}{P})$
再要求$t_{1}\equiv x_{1}(mod\ P)$，由于$\gcd(\frac{M}{P},P)=1$，根据性质3仍然存在$t_{1}$合法
根据$t_{1}$为新六元组的解有$t_{1}\equiv x_{1}(mod\ \frac{m_{1}}{P})$，再根据$t_{1}\equiv x_{1}(mod\ P)$，在这个同余方程中$x_{1}$显然为一组解，因此即得到$t_{1}\equiv x_{1}(mod\ m_{1})$，$t_{1}\equiv x_{2}(mod\ m_{2})$和$t_{1}\equiv x_{3}(mod\ m_{3})$根据$t_{1}$是新六元组的解即显然
性质4：对于素数$p$满足$ord_{p}(m_{1})\le ord_{p}(m_{2})$，则原六元组合法等价于$x_{1}\equiv x_{2}(mod\ P)$且$(\frac{m_{1}}{P},x_{1},m_{2},x_{2},m_{3},x_{3})$合法（其中$P=p^{ord_{p}(m_{1})}$）
证明：
原六元组若合法，根据$P\mid m_{1},m_{2}$即有$t\equiv x_{1}\equiv x_{2}(mod\ P)$，即要求$x_{1}\equiv x_{2}(mod\ P)$，且其$t$也可以作为新六元组的解，即新的六元组必然合法
当$x_{1}\equiv x_{2}(mod\ P)$且新六元组合法，对于其解$t_{0}$，有$t_{0}\equiv x_{2}\equiv x_{1}(mod\ P)$，再根据$t_{0}\equiv x_{1}(mod\ \frac{m_{1}}{P})$即可推出$t_{0}\equiv x_{1}(mod\ m_{1})$
同时$t_{0}\equiv x_{2}(mod\ m_{2})$和$t_{0}\equiv x_{3}(mod\ m_{3})$根据$t_{1}$是新六元组的解即显然，因此$t_{0}$也是原六元组的一组解，即原六元组合法
性质5：对于素数$p$，记$d_{i}=ord_{p}(m_{i})$，若有$d_{1}>\max(d_{2},d_{3})$，则原六元组合法等价于$(\frac{m_{1}}{p^{d_{1}-\max(d_{2},d_{3})}},x_{1},m_{2},x_{2},m_{3},x_{3})$合法
证明：
这即性质3和4的一个推论，具体来说——
根据性质4，原六元组合法等价于$x_{1}\equiv x_{2}(mod\ p^{d_{2}})$、$x_{1}\equiv x_{3}(mod\ p^{d_{3}})$以及$(m_{1},x_{1},\frac{m_{2}}{p^{d_{2}}},x_{2},\frac{m_{3}}{p^{d_{3}}},x_{3})$合法
再根据性质3，最后的这个六元组又等价于$(\frac{m_{1}}{p^{d_{1}-\max(d_{2},d_{3})}},x_{1},\frac{m_{2}}{p^{d_{2}}},x_{2},\frac{m_{3}}{p^{d_{3}}},x_{3})$合法
再根据性质4（将等价的两边交换），原六元组合法等价于$(\frac{m_{1}}{p^{d_{1}-\max(d_{2},d_{3})}},x_{1},m_{2},x_{2},m_{3},x_{3})$合法，即所求证
分析完这些性质后，我们回到原问题——
记$l_{i}=g_{i}+r_{i}$，$T=\prod_{i=1}^{3}l_{i}$，$L=lcm(l_{1},l_{2},l_{3})$，答案即
$$
\sum_{\forall 1\le i\le 3,0\le x_{i}<g_{i}且(l_{1},x_{1},l_{2},x_{2},l_{3},x_{3})合法,t为其一组解}\sum_{0\le j<T,j\equiv t(mod\ L)}1
$$
注意到在$[0,T)$中，恰好存在$\frac{T}{L}$个模$L$的完系，因此即
$$
\sum_{\forall 1\le i\le 3,0\le x_{i}<g_{i}且(l_{1},x_{1},l_{2},x_{2},l_{3},x_{3})合法}\frac{T}{L}
$$
现在我们仅关心于其是否合法，与其对应的解无关，因此可以根据性质5来调整$l_{1}$、$l_{2}$和$l_{3}$，调整后这三个数中每一个素数的指数较大的两个必然相等，因此最终一定可以被表示为$l_{1}=gab$、$l_{2}=gac$且$l_{3}=gbc$
（例如对于素数$p$，记$d_{i}=ord_{p}(l_{i})$，若$d_{1}=d_{2}\ge d_{3}$，令$g=p^{d_{3}}$且$a=p^{d_{1}-d_{3}}$即可）
关于合法，实际上也可以看作统计在$[0,gabc)$中满足其三个条件的解数（合法时恰好为1，不合法即为0），然后再调换枚举顺序，先去枚举每一组解，即
$$
\sum_{i=0}^{gabc-1}\prod_{j=1}^{3}\sum_{0\le k<g_{j},k\equiv i(mod\ l_{j})}\frac{T}{L}=\frac{T}{L}\sum_{i=0}^{gabc-1}\prod_{j=1}^{3}(\lfloor\frac{g_{j}}{l_{j}}\rfloor+[i\ mod\ l_{j}<g_{j}\ mod\ l_{j}])
$$
（注意$L\ne gabc$，所以这里所发生的变化并没有那么简单）
将后面这3个括号拆开，总共是8项，其中$\lfloor\frac{g_{j}}{l_{j}}\rfloor$为常数项，比较容易处理，这里直接考虑三项都是后面的非常数项的情况（一项或两项都类似）
此时，我们换一个角度去看待此问题：令$S_{j}=\{i\mid i\ mod\ l_{j}<g_{j}\ mod\ l_{j}\}$，即求$|S_{1}\cap S_{2}\cap S_{3}|$
关于$S_{j}$，也即$\bigcup_{0\le i<gabc,i\mid l_{j}}[i,i+g_{j}\ mod\ l_{j})$，也就是$\frac{gabc}{l_{j}}$个区间，不妨假设$a\le b\le c$，由于$l_{i}\le \max$，也即有$a,b\le \sqrt{\max}$，换言之$S_{2}$和$S_{3}$仅有$o(\sqrt{\max})$个区间，求交后也只有这么多
枚举其中的每一个个区间，统计$S_{1}$中对应的元素个数即可，复杂度为$o(\sqrt{\max})$，可以通过
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define N 2000005
4 #define ll long long
5 #define mod 998244353
6 #define fi first
7 #define se second
8 vector<pair<ll,ll> >v2,v3,v;
9 int T,s,ans,p[N],vis[N],d[4];
10 ll L,n,l[4],g[4],big[4];
11 ll gcd(ll x,ll y){
12 if (!y)return x;
13 return gcd(y,x%y);
14 }
15 int qpow(int n,int m){
16 int s=n,ans=1;
17 while (m){
18 if (m&1)ans=1LL*ans*s%mod;
19 s=1LL*s*s%mod;
20 m>>=1;
21 }
22 return ans;
23 }
24 int tot(ll x,ll y){
25 if (x/l[1]==y/l[1])return max((min(y%l[1],g[1]%l[1])-x%l[1]),0LL)%mod;
26 int s1=(max(g[1]%l[1]-x%l[1],0LL)+min(g[1]%l[1],y%l[1]))%mod;
27 int s2=(y/l[1]-x/l[1]-1)%mod*(g[1]%l[1]%mod)%mod;
28 return (s1+s2)%mod;
29 }
30 int main(){
31 for(int i=2;i<N;i++){
32 if (!vis[i])p[++p[0]]=i;
33 for(int j=1;(j<=p[0])&&(i*p[j]<N);j++){
34 vis[i*p[j]]=1;
35 if (i%p[j]==0)break;
36 }
37 }
38 T=L=1;
39 for(int i=1;i<=3;i++){
40 scanf("%lld%lld",&g[i],&l[i]);
41 l[i]+=g[i];
42 T=1LL*T*(l[i]%mod)%mod;
43 big[i]=l[i];
44 for(int j=1;j<=p[0];j++)
45 while (big[i]%p[j]==0)big[i]/=p[j];
46 }
47 for(int i=1;i<=3;i++){
48 bool flag=0;
49 for(int j=1;j<i;j++)
50 if (big[i]==big[j])flag=1;
51 if (!flag)L=1LL*L*(big[i]%mod)%mod;
52 for(int j=i+1;j<=3;j++)
53 if (big[i]==big[j])flag=1;
54 if (!flag)l[i]/=big[i];
55 }
56 for(int i=1;i<=p[0];i++){
57 d[1]=d[2]=d[3]=0;
58 for(int j=1;j<=3;j++){
59 ll k=l[j];
60 while (k%p[i]==0){
61 d[j]++;
62 k/=p[i];
63 }
64 }
65 for(int j=0;j<max(max(d[1],d[2]),d[3]);j++)L=1LL*L*p[i]%mod;
66 if (d[1]>max(d[2],d[3]))
67 for(int j=0;j<d[1]-max(d[2],d[3]);j++)l[1]/=p[i];
68 if (d[2]>max(d[1],d[3]))
69 for(int j=0;j<d[2]-max(d[1],d[3]);j++)l[2]/=p[i];
70 if (d[3]>max(d[1],d[2]))
71 for(int j=0;j<d[3]-max(d[1],d[2]);j++)l[3]/=p[i];
72 }
73 if (l[1]>l[2]){
74 swap(l[1],l[2]);
75 swap(g[1],g[2]);
76 }
77 if (l[1]>l[3]){
78 swap(l[1],l[3]);
79 swap(g[1],g[3]);
80 }
81 if (l[2]>l[3]){
82 swap(l[2],l[3]);
83 swap(g[2],g[3]);
84 }
85 ll G=gcd(gcd(l[1],l[2]),l[3]),a=gcd(l[1],l[2])/G,b=gcd(l[1],l[3])/G,c=gcd(l[2],l[3])/G;
86 n=G*a*b*c;
87 for(int i=1;i<=3;i++)d[i]=g[i]/l[i]%mod;
88 for(ll i=0;i<n;i+=l[2])v2.push_back(make_pair(i,i+g[2]%l[2]));
89 for(ll i=0;i<n;i+=l[3])v3.push_back(make_pair(i,i+g[3]%l[3]));
90 for(int i=0,j=0;i<v2.size();i++){
91 if (j)j--;
92 while ((j<v3.size())&&(v3[j].fi<v2[i].se)){
93 ll x=max(v2[i].fi,v3[j].fi),y=min(v2[i].se,v3[j].se);
94 if (x<y)v.push_back(make_pair(x,y));
95 j++;
96 }
97 }
98 ans=1LL*(n%mod)*d[1]%mod*d[2]%mod*d[3]%mod;
99 ans=(ans+1LL*d[1]*d[2]%mod*(n/l[3]*(g[3]%l[3])%mod))%mod;
100 ans=(ans+1LL*d[1]*(n/l[2]*(g[2]%l[2])%mod)%mod*d[3])%mod;
101 ans=(ans+1LL*(n/l[1]*(g[1]%l[1])%mod)*d[2]%mod*d[3])%mod;
102 s=0;
103 for(int i=0;i<v2.size();i++)s=(s+tot(v2[i].fi,v2[i].se))%mod;
104 ans=(ans+1LL*s*d[3])%mod;
105 s=0;
106 for(int i=0;i<v3.size();i++)s=(s+tot(v3[i].fi,v3[i].se))%mod;
107 ans=(ans+1LL*s*d[2])%mod;
108 s=0;
109 for(int i=0;i<v.size();i++)s=(s+v[i].se-v[i].fi)%mod;
110 ans=(ans+1LL*s*d[1])%mod;
111 for(int i=0;i<v.size();i++)ans=(ans+tot(v[i].fi,v[i].se))%mod;
112 ans=1LL*ans*T%mod*qpow(L,mod-2)%mod;
113 printf("%d",ans);
114 }
View Code