# BZOJ 4026 dC Loves Number Theory 分块+十字链表/可持久化线段树

#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 50500 #define B 700 #define MOD 1000777 using namespace std; struct abcd{ abcd *up,*rt; int p,belong; void* operator new (size_t) { static abcd mempool[M*7],*C=mempool; return C++; } }*head[M],*last[80800]; int n,m,b,last_ans; int a[M]; int prime[80800],tot; long long inv[MOD]; int l[M],belong[M]; int prod[B][M]; void Linear_Shaker() { static bool not_prime[1001001]; int i,j; for(i=2;i<=1000000;i++) { if(!not_prime[i]) prime[++tot]=i; for(j=1;prime[j]*i<=1000000;j++) { not_prime[prime[j]*i]=true; if(i%prime[j]==0) break; } } for(inv[1]=1,i=2;i<MOD;i++) inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD; } abcd* Decomposition(int pos) { int i,n=a[pos]; abcd *re=0x0; for(i=1;prime[i]*prime[i]<=n;i++) if(n%prime[i]==0) { abcd *temp=new abcd; temp->up=re; temp->p=i; temp->belong=pos; if(last[i]) last[i]->rt=temp; re=last[i]=temp; while(n%prime[i]==0) n/=prime[i]; } if(n!=1) { i=lower_bound(prime+1,prime+tot+1,n)-prime; abcd *temp=new abcd; temp->up=re; temp->p=i; temp->belong=pos; if(last[i]) last[i]->rt=temp; re=last[i]=temp; } return re; } int Query(int x,int y) { int i,st=belong[x-1]+1,re=inv[a[x-1]]*a[y]%MOD; abcd *temp; if(y>=l[st]) re=(long long)re*prod[st][y]%MOD; for(i=min(y,l[st]-1);i>=x;i--) for(temp=head[i];temp;temp=temp->up) if(!temp->rt||temp->rt->belong>y) re=re*inv[prime[temp->p]]%MOD*(prime[temp->p]-1)%MOD; return re; } namespace IStream{ const int L=1<<15; char buffer[L],*S,*T; inline char Get_Char() { if(S==T) { T=(S=buffer)+fread(buffer,1,L,stdin); if(S==T) return EOF; } return *S++; } inline int Get_Int() { char c; int re=0; for(c=Get_Char();c<'0'||c>'9';c=Get_Char()); while(c>='0'&&c<='9') re=(re<<1)+(re<<3)+(c-'0'),c=Get_Char(); return re; } } int main() { using namespace IStream; int i,j,x,y; abcd *temp; cin>>n>>m; b=200; Linear_Shaker(); for(i=1;i<=n;i++) { a[i]=Get_Int(); head[i]=Decomposition(i); } for(a[0]=1,i=1;i<=n;i++) a[i]=(long long)a[i]*a[i-1]%MOD; for(i=1;i<=n;i++) belong[i]=(i-1)/b+1; for(i=1;i<=belong[n];i++) l[i]=(i-1)*b+1; l[i]=0x3f3f3f3f; static int v[80800],ans; for(j=1;j<=belong[n];j++) { ans=1; for(i=l[j];i<=n;i++) { for(temp=head[i];temp;temp=temp->up) if(v[temp->p]!=j) { v[temp->p]=j; ans = ans * inv[prime[temp->p]] % MOD * (prime[temp->p]-1) % MOD ; } prod[j][i]=ans; } } 

 for(i=1;i<=m;i++) { x=Get_Int(); y=Get_Int(); x^=last_ans; y^=last_ans; printf("%d ",last_ans=Query(x,y)); } //puts("Fuck♂You!"); return 0; }

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，您必须在下载后24小时内删除！
3. 不得使用于非法商业用途，不得违反国家法律。否则后果自负！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 如遇到加密压缩包，请使用WINRAR解压,如遇到无法解压的请联系管理员！