智慧樹

• 解決此題有兩個要點：

如何判斷一個線性同余方程組有沒有解

如何統(tǒng)計合法子序列數(shù)目

• 先看第2點：
  若一個序列是合法的，則這個序列的所有子序列都是合法的
  考慮對$?1\le i\le n$，求出以$i$為左端點時，序列右端點最右能取到哪，記為$nxt[i]$
  若不考慮$l,r$的限制，所有合法子序列數(shù)=${\sum }_{i=1}^n(nxt[i]?i+1)$
• 加入$l,r$的限制，相當于限制了：
  1.序列左端點必須$\ge l$
  2.序列右端點必須$\le r$
  兩個限制不好同時處理，我們考慮分開處理：
  -采用離線做法，把詢問按$l$從大到小排序，對每個詢問，只考慮 序列左端點$i\ge$當前的$l$ 的序列，這樣便可保證滿足第一個限制。
  -對于第二個限制，維護$cnt[j]$表示 $j$是多少個 當前納入考慮的合法序列 的右端點，則詢問$(l,r)$的答案為${\sum }_{j=l}^{r}cnt[j]$
  以上可以用線段樹/樹狀數(shù)組維護（樹狀數(shù)組的區(qū)間修改、區(qū)間查詢戳這里）。
• 再看第1點：

樸素做法：
既然不保證$m_i$為質(zhì)數(shù)，那么就不能用$CRT$，只能用$exCRT$了
考慮方程組：
$\{\begin{array}{l}x\equiv b_1(\mathrm{m}\mathrm{o}\mathrm{d}{m}_1)\\ x\equiv b_2(\mathrm{m}\mathrm{o}\mathrm{d}{m}_2)\end{array}$
則$x=m_1{k}_1+b_1=m_2{k}_2+b_2$
$\therefore m_1{k}_1?m_2{k}_2=b_2?b_1$
由拓展歐幾里得知，$k_1,k_2$有解，當且僅當$|b_2?b_1|=gcd(m_1,m_2)$
若$k_1,k_2$有解，我們可以得到一個同時符合兩條方程的$x$值，設為$x^{\prime }$
那么兩個方程可以合并為一個新的方程：
$x\equiv x^{\prime }(\mathrm{m}\mathrm{o}\mathrm{d}lcm(m_1,m_2))$
用新方程再去和其它方程合并即可（ps：合并方程求$nxt$的過程可以用ST表優(yōu)化）

正解：
當$M$較大時，由于解的模數(shù)較大，不宜基于求解來維護線性同余方程組。事實上，“求解”浪費了信息，我們只需要知道“是否有解”。

• 先考慮 $m_i$均為素數(shù) 的特殊情況：
  一個方程組無解，當且僅當方程組中存在兩個方程：
  $x\equiv b_i(\mathrm{m}\mathrm{o}\mathrm{d}p)$，$x\equiv b_j(\mathrm{m}\mathrm{o}\mathrm{d}p)$，且$b_i!=b_j$
  為求$nxt$，我們維護一個由線性同余方程構成的隊列，支持入隊、出隊和查詢這些方程構成的方程組加上一個新方程組是否有解。
  而判斷方程組有沒有解，我們只需對每個素數(shù)$p$維護 目前限制$x\mathrm{m}\mathrm{o}\mathrm{d}p$的余數(shù)是什么、對$x\mathrm{m}\mathrm{o}\mathrm{d}p$的余數(shù)的限制有幾個 即可
• 再考慮 $m_i$為任意正整數(shù) 的情況：
  假設$m_i={\prod }_{j=1}{p}_j^{a_j}$（$p$表示素數(shù)），
  則方程$x\equiv b_i(\mathrm{m}\mathrm{o}\mathrm{d}{m}_i)$可以分解成：
  $?\begin{array}{l}x\equiv b_i(\mathrm{m}\mathrm{o}\mathrm{d}{p}_1^{a_1})\\ x\equiv b_i(\mathrm{m}\mathrm{o}\mathrm{d}{p}_2^{a_2})\\ x\equiv b_i(\mathrm{m}\mathrm{o}\mathrm{d}{p}_3^{a_3})\\ ...\end{array}$
  那么一個方程組無解，當且僅當方程組中存在兩個方程：
  $x\equiv b_i(\mathrm{m}\mathrm{o}\mathrm{d}{p}^a)$，$x\equiv b_j(\mathrm{m}\mathrm{o}\mathrm{d}{p}^a)$，且$b_i!=b_j$
  做法類似上面，對每個$p^a$維護 目前限制$x\mathrm{m}\mathrm{o}\mathrm{d}{p}^a$的余數(shù)是什么、對$x\mathrm{m}\mathrm{o}\mathrm{d}{p}^a$的余數(shù)的限制有幾個 即可

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int N=1e6+10; int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } int pri[N],cnt,vis[N],mn[N]; int n,m[N],b[N],q; int lim[N],tot[N],nxt[N]; //nxt[i]記錄以i為區(qū)間左端點,區(qū)間右端點最右能取到哪 struct Que{int l,r,id;friend bool operator < (Que a,Que b){return a.l<b.l;} }que[N]; ll ans[N]; void init(){vis[0]=vis[1]=1;for(int i=2;i<=1000000;i++){if(!vis[i]){pri[++cnt]=i;mn[i]=i;}for(int j=1;j<=cnt,pri[j]*i<=1000000;j++){vis[pri[j]*i]=1;mn[i*pri[j]]=pri[j];if(i%pri[j]==0) break;}} } void del(int i){int tmp=m[i];while(tmp!=1){int fac=mn[tmp],pw=1;while(tmp%fac==0){tmp/=fac;pw*=fac;}for(int k=pw;k>=1;k/=fac){tot[k]--;if(!tot[k]) lim[k]=-1;}} } void get_nxt(){memset(lim,-1,sizeof(lim));int j=n+1;for(int i=n;i>=1;i--){int tmp=m[i];while(tmp!=1){int fac=mn[tmp],pw=1;while(tmp%fac==0){tmp/=fac;pw*=fac;}for(int k=pw;k>=1;k/=fac){if(lim[k]!=-1&&lim[k]!=b[i]%k){while(lim[k]!=-1) del(--j);}}for(int k=pw;k>=1;k/=fac){tot[k]++;if(lim[k]==-1) lim[k]=b[i]%k;}}nxt[i]=j-1;//i最右能和j-1合并 }for(int i=n-1;i>=1;i--) nxt[i]=min(nxt[i],nxt[i+1]); } namespace SegmentTree{ll sum[N<<2],tag[N<<2];void pushdown(int u,int l,int r){if(tag[u]){int mid=(l+r)>>1;sum[u<<1]+=tag[u]*(mid-l+1);tag[u<<1]+=tag[u];sum[u<<1|1]+=tag[u]*(r-mid);tag[u<<1|1]+=tag[u];tag[u]=0;}}void add(int u,int l,int r,int a,int b,int x){if(a<=l&&r<=b){sum[u]+=x*(r-l+1);tag[u]+=x;return;}pushdown(u,l,r);int mid=(l+r)>>1;if(a<=mid) add(u<<1,l,mid,a,b,x);if(b>mid) add(u<<1|1,mid+1,r,a,b,x);sum[u]=sum[u<<1]+sum[u<<1|1];}ll query(int u,int l,int r,int a,int b){if(a<=l&&r<=b) return sum[u];pushdown(u,l,r);int mid=(l+r)>>1;ll res=0;if(a<=mid) res+=query(u<<1,l,mid,a,b);if(b>mid) res+=query(u<<1|1,mid+1,r,a,b);return res;} }; using namespace SegmentTree; int main(){init();n=read();for(int i=1;i<=n;i++)m[i]=read(),b[i]=read();get_nxt();q=read();for(int i=1;i<=q;i++){que[i].l=read();que[i].r=read();que[i].id=i;}sort(que+1,que+q+1);int tmp=n+1;for(int i=q;i>=1;i--){while(tmp>1&&tmp-1>=que[i].l){tmp--;add(1,1,n,tmp,nxt[tmp],1);//以tmp~nxt[tmp]為右端點的區(qū)間都多了一個 }ans[que[i].id]=query(1,1,n,que[i].l,que[i].r);}for(int i=1;i<=q;i++) printf("%lld\n",ans[i]);return 0; }

總結(jié)

以上是生活随笔為你收集整理的[XSY] 智慧树（线性同余方程组，线段树/树状数组）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。