P5071 [Ynoi2015] 此时此刻的光辉
tag：莫队，根号分治
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;
const int MOD=19260817;
const int maxn=1e5+5;
const int maxm=31635;
const int S=1000;
int p[maxm],raw[maxn<<1],cnt[maxn<<1],pos[maxn],s[maxn][175],len,Num,up,n,m,P,l=1,r;
struct node{int l,r,id;}q[maxn];
ll ans[maxn],inv[maxn],now=1;
vector<int>fac[maxn],Cnt[maxn];
bool vis[maxm];
bool cmp(node a,node b){
if(pos[a.l]==pos[b.l]){
if(pos[a.l]&1) return a.r>b.r;
return a.r<b.r;
}
return a.l<b.l;
}
void add(int i){
for(int j=0;j<fac[i].size();j++){
int p=fac[i][j],R=Cnt[i][j];
now=(now*inv[cnt[p]+1])%MOD;
cnt[p]+=R;
now=(now*(cnt[p]+1))%MOD;
}
}
void del(int i){
for(int j=0;j<fac[i].size();j++){
int p=fac[i][j],R=Cnt[i][j];
now=(now*inv[cnt[p]+1])%MOD;
cnt[p]-=R;
now=(now*(cnt[p]+1))%MOD;
}
}
int main(){
int N=31634;
for(int i=2;i<=N;i++){
if(!vis[i]) p[++len]=i;
if(i==1000) up=len;
for(int j=i*i;j<=N;j+=i)
vis[j]=true;
}
inv[1]=1;
scanf("%d%d",&n,&m);
for(int i=2;i<=2*n;i++)
inv[i]=((MOD-MOD/i)*inv[MOD%i])%MOD;
int P=max(n/max((int)sqrt(m),1),1);
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
pos[i]=(i-1)/P+1;
for(int j=1;j<=up;j++) s[i][j]=s[i-1][j];
for(int j=1;j<=len&&p[j]*p[j]<=x;j++){
if(x%p[j]==0){
int num=0;
while(x%p[j]==0){
x/=p[j];
num++;
}
if(p[j]>S){
fac[i].push_back(p[j]);
Cnt[i].push_back(num);
raw[++Num]=p[j];
}
else s[i][j]+=num;
}
}
if(x!=1){
if(x>S){
fac[i].push_back(x);
Cnt[i].push_back(1);
raw[++Num]=x;
}
else s[i][lower_bound(p+1,p+len+1,x)-p]++;
}
}
sort(raw+1,raw+Num+1);
int Len=unique(raw+1,raw+Num+1)-raw-1;
for(int i=1;i<=n;i++)
for(int j=0;j<fac[i].size();j++)
fac[i][j]=lower_bound(raw+1,raw+Len+1,fac[i][j])-raw;
for(int i=1;i<=m;i++){
scanf("%d%d",&q[i].l,&q[i].r);
q[i].id=i;
}
sort(q+1,q+m+1,cmp);
for(int i=1;i<=m;i++){
int x=q[i].l,y=q[i].r;
while(r<y) add(++r);
while(l>x) add(--l);
while(l<x) del(l++);
while(r>y) del(r--);
ans[q[i].id]=now;
for(int j=1;j<=up;j++)
ans[q[i].id]=(ans[q[i].id]*(s[q[i].r][j]-s[q[i].l-1][j]+1))%MOD;
}
for(int i=1;i<=m;i++)
printf("%lld\n",ans[i]);
return 0;
}
P3934 [Ynoi2016] 炸脖龙 I
tag：树状数组，扩展欧拉定理，线性筛
#include<iostream>
#include<cstdio>
#define lowbit(x) x&(-x)
using namespace std;
typedef long long ll;
const int maxn=5e5+5;
const int maxm=2e7+5;
int a[maxn],p[maxm],phi[maxm],len,n,m;
struct node{ll v;bool flag;};
bool vis[maxm];
ll t[maxn];
void prework(int N){
// phi[1]=1;
for(int i=2;i<=N;i++){
if(!vis[i]){
p[++len]=i;
phi[i]=i-1;
}
for(int j=1;j<=len&&p[j]<=N/i;j++){
vis[i*p[j]]=true;
if(i%p[j]==0){
phi[i*p[j]]=phi[i]*p[j];
break;
}
phi[i*p[j]]=phi[i]*(p[j]-1);
}
}
}
void add(int x,int k){
for(;x<=n;x+=lowbit(x)) t[x]+=k;
}
ll query(int x){
ll ans=0;
for(;x;x-=lowbit(x)) ans+=t[x];
return ans;
}
node power(ll a,ll b,ll p){
node ans=(node){1,0};
if(a>=p){
a%=p;
ans.flag=1;
}
for(;b;b>>=1){
if(b&1){
ans.v*=a;
if(ans.v>=p){
ans.v%=p;
ans.flag=1;
}
}
a=a*a;
if(a>=p){
a%=p;
ans.flag=1;
}
}
return ans;
}
node solve(int l,int r,int p){
if(p==1) return (node){0,1};
ll val=query(l);
if(l==r){
if(val>=p) return (node){val%p,1};
return (node){val,0};
}
node res=solve(l+1,r,phi[p]);
if(res.flag) res.v+=phi[p];
return power(val,res.v,p);
}
int main(){
prework(20000000);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
add(i,a[i]-a[i-1]);
while(m--){
int opt,l,r,k,p;
scanf("%d%d%d",&opt,&l,&r);
if(opt&1){
scanf("%d",&k);
add(l,k);
add(r+1,-k);
}
else{
scanf("%d",&p);
printf("%lld\n",solve(l,r,p).v);
}
}
return 0;
}
P5309 [Ynoi2011] 初始化
tag：分块，根号分治，前缀和
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
const int maxm=450;
const int MOD=1e9+7;
ll sum[maxm],a[maxn],pre[maxm][maxm],suf[maxm][maxm];
int pos[maxn],n,m,p;
ll query(int l,int r){
ll ans=0;
for(int i=l;i<=min(r,pos[l]*p);i++) ans+=a[i];
if(pos[l]==pos[r]) return ans;
for(int i=(pos[r]-1)*p+1;i<=r;i++) ans+=a[i];
for(int i=pos[l]+1;i<pos[r];i++) ans+=sum[i];
return ans;
}
void update(int x,int y,int z){
if(x>=p){
for(int i=y;i<=n;i+=x){
a[i]+=z;
sum[pos[i]]+=z;
}
return;
}
for(int i=y;i<=x;i++) pre[x][i]+=z;
for(int i=y;i>=1;i--) suf[x][i]+=z;
}
ll Query(int l,int r){
ll ans=query(l,r);
for(int i=1;i<p;i++){
int posl=(l-1)/i+1,posr=(r-1)/i+1;
if(posl==posr) ans+=(pre[i][(r-1)%i+1]-pre[i][(l-1)%i]);
else ans+=(1ll*(posr-posl-1)*pre[i][i]+suf[i][(l-1)%i+1]+pre[i][(r-1)%i+1]);
}
return ans;
}
int main(){
scanf("%d%d",&n,&m);
p=max((int)sqrt(n),1);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
pos[i]=(i-1)/p+1;
sum[pos[i]]+=a[i];
}
while(m--){
int opt,x,y,z,l,r;
scanf("%d",&opt);
if(opt&1){
scanf("%d%d%d",&x,&y,&z);
update(x,y,z);
}
else{
scanf("%d%d",&l,&r);
printf("%lld\n",Query(l,r)%MOD);
}
}
return 0;
}