贵阳做网站seo,免费域名注册和免费建站,扁平化设计风格的网站模板免费下载,电子商务网站推广的主要方法智慧树
解决此题有两个要点#xff1a;
如何判断一个线性同余方程组有没有解如何统计合法子序列数目
先看第2点#xff1a; 若一个序列是合法的#xff0c;则这个序列的所有子序列都是合法的 考虑对∀1≤i≤n\forall 1\leq i\leq n∀1≤i≤n#xff0c;求出以iii为左端点…智慧树
解决此题有两个要点
如何判断一个线性同余方程组有没有解如何统计合法子序列数目
先看第2点 若一个序列是合法的则这个序列的所有子序列都是合法的 考虑对∀1≤i≤n\forall 1\leq i\leq n∀1≤i≤n求出以iii为左端点时序列右端点最右能取到哪记为nxt[i]nxt[i]nxt[i] 若不考虑l,rl,rl,r的限制所有合法子序列数∑i1n(nxt[i]−i1)\sum_{i1}^{n}(nxt[i]-i1)∑i1n(nxt[i]−i1)加入l,rl,rl,r的限制相当于限制了 1.序列左端点必须≥l\geq l≥l 2.序列右端点必须≤r\leq r≤r 两个限制不好同时处理我们考虑分开处理 -采用离线做法把询问按lll从大到小排序对每个询问只考虑 序列左端点i≥i\geqi≥当前的lll 的序列这样便可保证满足第一个限制。 -对于第二个限制维护cnt[j]cnt[j]cnt[j]表示 jjj是多少个 当前纳入考虑的合法序列 的右端点则询问(l,r)(l,r)(l,r)的答案为∑jlrcnt[j]\sum_{jl}^{r}cnt[j]∑jlrcnt[j] 以上可以用线段树/树状数组维护树状数组的区间修改、区间查询戳这里。再看第1点
朴素做法 既然不保证mim_imi为质数那么就不能用CRTCRTCRT只能用exCRTexCRTexCRT了 考虑方程组 {x≡b1(modm1)x≡b2(modm2)\begin{cases}x\equiv b_1(\mod m_1) \\x\equiv b_2(\mod m_2)\end{cases}{x≡b1(modm1)x≡b2(modm2) 则xm1k1b1m2k2b2xm_1k_1b_1m_2k_2b_2xm1k1b1m2k2b2 ∴m1k1−m2k2b2−b1\therefore m_1k_1-m_2k_2b_2-b_1∴m1k1−m2k2b2−b1 由拓展欧几里得知k1,k2k_1,k_2k1,k2有解当且仅当∣b2−b1∣gcd(m1,m2)|b_2-b_1|gcd(m_1,m_2)∣b2−b1∣gcd(m1,m2) 若k1,k2k_1,k_2k1,k2有解我们可以得到一个同时符合两条方程的xxx值设为x′xx′ 那么两个方程可以合并为一个新的方程 x≡x′(modlcm(m1,m2))x\equiv x(\mod lcm(m_1,m_2))x≡x′(modlcm(m1,m2)) 用新方程再去和其它方程合并即可ps合并方程求nxtnxtnxt的过程可以用ST表优化正解 当MMM较大时由于解的模数较大不宜基于求解来维护线性同余方程组。事实上“求解”浪费了信息我们只需要知道“是否有解”。
先考虑 mim_imi均为素数 的特殊情况 一个方程组无解当且仅当方程组中存在两个方程 x≡bi(modp)x\equiv b_i(\mod p)x≡bi(modp)x≡bj(modp)x\equiv b_j(\mod p)x≡bj(modp)且bi!bjb_i!b_jbi!bj 为求nxtnxtnxt我们维护一个由线性同余方程构成的队列支持入队、出队和查询这些方程构成的方程组加上一个新方程组是否有解。 而判断方程组有没有解我们只需对每个素数ppp维护 目前限制xmodpx \mod pxmodp的余数是什么、对xmodpx \mod pxmodp的余数的限制有几个 即可再考虑 mim_imi为任意正整数 的情况 假设mi∏j1pjajm_i\prod_{j1}p_j^{a_j}mi∏j1pjajppp表示素数 则方程x≡bi(modmi)x\equiv b_i(\mod m_i)x≡bi(modmi)可以分解成 {x≡bi(modp1a1)x≡bi(modp2a2)x≡bi(modp3a3)...\begin{cases}x\equiv b_i(\mod p_1^{a_1}) \\x\equiv b_i(\mod p_2^{a_2})\\x\equiv b_i(\mod p_3^{a_3})\\...\end{cases}⎩⎪⎪⎪⎨⎪⎪⎪⎧x≡bi(modp1a1)x≡bi(modp2a2)x≡bi(modp3a3)... 那么一个方程组无解当且仅当方程组中存在两个方程 x≡bi(modpa)x\equiv b_i(\mod p^a)x≡bi(modpa)x≡bj(modpa)x\equiv b_j(\mod p^a)x≡bj(modpa)且bi!bjb_i!b_jbi!bj 做法类似上面对每个pap^apa维护 目前限制xmodpax \mod p^axmodpa的余数是什么、对xmodpax \mod p^axmodpa的余数的限制有几个 即可
#includeiostream
#includecstdio
#includecstring
#includealgorithm
using namespace std;
typedef long long ll;
const int N1e610;
int read(){int x0,f1;char chgetchar();while(ch0||ch9){if(ch-)f-1;chgetchar();}while(ch0ch9){xx*10ch-0;chgetchar();}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为区间左端点,区间右端点最右能取到哪
struct Que{int l,r,id;friend bool operator (Que a,Que b){return a.lb.l;}
}que[N];
ll ans[N];
void init(){vis[0]vis[1]1;for(int i2;i1000000;i){if(!vis[i]){pri[cnt]i;mn[i]i;}for(int j1;jcnt,pri[j]*i1000000;j){vis[pri[j]*i]1;mn[i*pri[j]]pri[j];if(i%pri[j]0) break;}}
}
void del(int i){int tmpm[i];while(tmp!1){int facmn[tmp],pw1;while(tmp%fac0){tmp/fac;pw*fac;}for(int kpw;k1;k/fac){tot[k]--;if(!tot[k]) lim[k]-1;}}
}
void get_nxt(){memset(lim,-1,sizeof(lim));int jn1;for(int in;i1;i--){int tmpm[i];while(tmp!1){int facmn[tmp],pw1;while(tmp%fac0){tmp/fac;pw*fac;}for(int kpw;k1;k/fac){if(lim[k]!-1lim[k]!b[i]%k){while(lim[k]!-1) del(--j);}}for(int kpw;k1;k/fac){tot[k];if(lim[k]-1) lim[k]b[i]%k;}}nxt[i]j-1;//i最右能和j-1合并 }for(int in-1;i1;i--) nxt[i]min(nxt[i],nxt[i1]);
}
namespace SegmentTree{ll sum[N2],tag[N2];void pushdown(int u,int l,int r){if(tag[u]){int mid(lr)1;sum[u1]tag[u]*(mid-l1);tag[u1]tag[u];sum[u1|1]tag[u]*(r-mid);tag[u1|1]tag[u];tag[u]0;}}void add(int u,int l,int r,int a,int b,int x){if(alrb){sum[u]x*(r-l1);tag[u]x;return;}pushdown(u,l,r);int mid(lr)1;if(amid) add(u1,l,mid,a,b,x);if(bmid) add(u1|1,mid1,r,a,b,x);sum[u]sum[u1]sum[u1|1];}ll query(int u,int l,int r,int a,int b){if(alrb) return sum[u];pushdown(u,l,r);int mid(lr)1;ll res0;if(amid) resquery(u1,l,mid,a,b);if(bmid) resquery(u1|1,mid1,r,a,b);return res;}
};
using namespace SegmentTree;
int main(){init();nread();for(int i1;in;i)m[i]read(),b[i]read();get_nxt();qread();for(int i1;iq;i){que[i].lread();que[i].rread();que[i].idi;}sort(que1,queq1);int tmpn1;for(int iq;i1;i--){while(tmp1tmp-1que[i].l){tmp--;add(1,1,n,tmp,nxt[tmp],1);//以tmp~nxt[tmp]为右端点的区间都多了一个 }ans[que[i].id]query(1,1,n,que[i].l,que[i].r);}for(int i1;iq;i) printf(%lld\n,ans[i]);return 0;
}
