2 条题解
-
0
鬼知道我加了多少优化操作卡过去的。
#include<bits/stdc++.h> using namespace std; #define int long long const int N=1e5+10,P=19260817; bool v[N+10];int p[N],pr,inv[N*16];map<int,int>mp; void init() { pr=0;memset(v,0,sizeof(v)); for(int i=2;i<=N/2;i++) { if(!v[i])p[++pr]=i,mp[i]=pr; for(int j=1;(j<=pr)&&(i*p[j]<=N/2);j++) { v[i*p[j]]=1; if(i%p[j]==0)break; } } inv[1]=1; for(int i=2;i<=(N-10)*16;i++) inv[i]=(P-P/i)*inv[P%i]%P; } int cnt[N],sum,B,a[N],len; int qpow(int a,int b){int ans=1;for(;b;b>>=1,a=a*a%P)if(b&1)ans=ans*a%P;return ans;} struct node{int x,y;};vector<node>G[N]; struct node1{int l,r,id;}q[N];int ans[N]; bool cmp(node1 n1,node1 n2){return n1.l/B!=n2.l/B?n1.l<n2.l:(n1.l/B)&1?n1.r<n2.r:n1.r>n2.r;} void add(int x) { for(auto i:G[x]) { sum=sum*inv[cnt[i.x]+1]%P; cnt[i.x]+=i.y; sum=sum*(cnt[i.x]+1)%P; } } void del(int x) { for(auto i:G[x]) { sum=sum*inv[cnt[i.x]+1]%P; cnt[i.x]-=i.y; sum=sum*(cnt[i.x]+1)%P; } } signed main() { init();sum=1;len=pr; int n,m;cin>>n>>m;B=n/sqrt(m); for(int i=1;i<=n;i++) { cin>>a[i];int x=a[i]; for(int j=1;j<=pr&&x!=1&&p[j]*p[j]<=x;j++)if(x%p[j]==0) { int s1=0; while(x%p[j]==0)x/=p[j],s1++; G[i].push_back({mp[p[j]],s1}); } if(x!=1) { if(!mp[x])mp[x]=++len; G[i].push_back({mp[x],1}); } } for(int i=1;i<=m;i++)cin>>q[i].l>>q[i].r,q[i].id=i; sort(q+1,q+m+1,cmp); for(int i=1,l=1,r=0;i<=m;i++) { while(l>q[i].l)add(--l); while(r<q[i].r)add(++r); while(l<q[i].l)del(l++); while(r>q[i].r)del(r--); ans[q[i].id]=sum; } for(int i=1;i<=m;i++)cout<<ans[i]<<'\n'; return 0; } -
0
在太阳西斜的这个世界里，置身天上之森。等这场战争结束之后，不归之人与望眼欲穿的众人， 人人本着正义之名，长存不灭的过去、逐渐消逝的未来。我回来了，纵使日薄西山，即便看不到未来，此时此刻的光辉，盼君勿忘。————世界上最幸福的女孩
我永远喜欢珂朵莉。
以内的数最多有10个不同的质因子。
考虑对其质因数分解。
由于值域范围过大，考虑使用Pollard-Rho算法。
这里普通的Pollard-Rho算法可能会TLE。如果你的代码能通过模板题，那基本上没问题（
窝反正直接把以前写的板子拉过来然后调了调参）。之后，你就会得到最多个不同的质因数。对其进行离散化，开桶记录。
然后上莫队，对于每次指针的偏移，把它所有的质因数加到桶里，同时维护约数个数即可。
这部分时间复杂度，加上上面的质因数分解的玄学期望复杂度，只能获得82分的好成绩。
我们考虑把每个数以内的质因子先取出来（以内共168个质数），然后，对其做前缀和，记录前缀的出现次数。
然后，由于，所以每个数剩下最多不超过2个质因子。这部分用Pollard_Rho找即可。
然后莫队的时候，对于前面168个质数就可以不用维护，直接用前缀和。
而对于后面的大质因子，再离散化处理即可。由于每个数最多两个质因子，所以常数就小了很多。
而由于筛掉了很多小的质因子，Pollard_Rho的速度也会变快。然后就足以通过此题。
Code：
#include<cctype> #include<cstdio> #include<cstdlib> #include<algorithm> #include<vector> #include<cstring> #define ctz __builtin_ctz using namespace std; #ifdef ONLINE_JUDGE struct istream{ char buf[23333333],*s; inline istream(){ buf[fread(s=buf,1,23333330,stdin)]='\n'; fclose(stdin); } inline istream&operator>>(int&d){ d=0; for(;!isdigit(*s);++s); while(isdigit(*s)) d=(d<<3)+(d<<1)+(*s++^'0'); return*this; } }cin; struct ostream{ char buf[8000005],*s; inline ostream(){s=buf;} inline ostream&operator<<(int d){ if(!d){ *s++='0'; }else{ static int w; for(w=1;w<=d;w*=10); for(;w/=10;d%=w)*s++=d/w^'0'; } return*this; } inline ostream&operator<<(const char&c){*s++=c;return*this;} inline void flush(){ fwrite(buf,1,s-buf,stdout); s=buf; } inline~ostream(){flush();} }cout; #else #include<iostream> #endif int pri[170],cct=0,sum[100005][169],num[1005]; void sieve(){ for(int i=2;i<=1000;++i)num[i]=1; for(int i=2;i<=1000;++i) if(num[i]){ pri[num[i]=++cct]=i; for(int j=i<<1;j<=1000;j+=i)num[j]=0; } } using LoveLive=long long; vector<int>tj; const int pr[]={2,3,5,7,11,13,17}; int gcd(int a,int b){ if(!a||!b)return a|b; int t=ctz(a|b); a>>=ctz(a); do{ b>>=ctz(b); if(a>b)swap(a,b); b-=a; }while(b); return a<<t; } inline int power(int a,int b,const int&md){ int ans=1; for(;b;b>>=1){ if(b&1)ans=(LoveLive)ans*a%md; a=(LoveLive)a*a%md; } return ans; } int miller_rabin(int p){ if(p==2)return 1; int b=p-1; int t=0; while(!(b&1))b>>=1,++t; for(int i:pr){ int r=power(i%(p-2)+2,b,p); if(r==1||r==p-1)continue; int ok=1; for(int j=1;j<=t&&ok;++j){ r=(LoveLive)r*r%p; if(r==p-1)ok=0; } if(ok)return 0; } return 1; } void pollard_rho(int&n,int c){ int k=2,x=rand()%(n-1)+1,y=x,q=1,t=1; for(;;k<<=1,y=x,q=1){ for(int i=1;i<=k;++i){ x=((LoveLive)x*x%n+c)%n; q=(LoveLive)q*abs(x-y)%n; if(!(i&63)){ t=gcd(q,n); if(t>1)break; } } if(t>1||(t=gcd(q,n))>1)break; } n=t; } void find(int n,int c){ if(n==1)return; if(miller_rabin(n)){tj.push_back(n);return;} int p=n; while(p>=n)pollard_rho(p,c--); n/=p; tj.push_back(n),tj.push_back(p); } #define N 100005 const int md=19260817; int n,m,a[N],inv[N*3],cnt[N],tot[N*2],now=1,ans[N]; int p[N][3]; vector<int>lr; struct que{ static const int siz=317; int l,r,id; inline bool operator<(const que&rhs)const{ return((l/siz!=rhs.l/siz)?(l<rhs.l):r<rhs.r); } }q[N]; inline void add(int id){ for(register int i=1;i<=cnt[id];++i) now=(LoveLive)now*inv[tot[p[id][i]]]%md*(tot[p[id][i]]+1)%md,++tot[p[id][i]]; } inline void del(int id){ for(register int i=1;i<=cnt[id];++i) now=(LoveLive)now*inv[tot[p[id][i]]]%md*(tot[p[id][i]]-1)%md,--tot[p[id][i]]; } int main(){ srand(19260817); sieve(); cin>>n>>m; inv[1]=1; for(int i=2;i<=3*n;++i)inv[i]=(md-md/i)*1LL*inv[md%i]%md; for(int i=1;i<=n;++i){ cin>>a[i]; memcpy(sum[i],sum[i-1],sizeof*sum); for(int j=1;j<=cct&&pri[j]*pri[j]<=a[i];++j) while(!(a[i]%pri[j])){ ++sum[i][j]; a[i]/=pri[j]; } if(a[i]>1){ if(a[i]<=pri[cct]){ ++sum[i][num[a[i]]]; continue; } tj.clear(); find(a[i],23333); for(int it:tj) p[i][++cnt[i]]=it,lr.push_back(it); } } sort(lr.begin(),lr.end()); lr.erase(unique(lr.begin(),lr.end()),lr.end()); for(int i=1;i<=n;++i) for(int j=1;j<=cnt[i];++j)p[i][j]=lower_bound(lr.begin(),lr.end(),p[i][j])-lr.begin(); for(int i=1;i<=m;++i)cin>>q[q[i].id=i].l>>q[i].r; sort(q+1,q+m+1); for(int i=0;i<n<<1;++i)tot[i]=1; for(int i=1,l=1,r=0;i<=m;++i){ while(r<q[i].r)add(++r); while(r>q[i].r)del(r--); while(l>q[i].l)add(--l); while(l<q[i].l)del(l++); int&out=ans[q[i].id];out=now; for(int j=1;j<=cct;++j) out=(LoveLive)out*(sum[r][j]-sum[l-1][j]+1)%md; } for(int i=1;i<=m;++i) cout<<ans[i]<<'\n'; return 0; }
qinkaiwen
LV 10
MOD
@ 2026-8-22 9:31:40
- 1