【BZOJ】【P 813】【奇数国】【題解】【樹状配列】
1527 ワード
転送ゲート:http://www.lydsy.com/JudgeOnline/problem.php?id=3813
お互いに、phi、なくなりました
60本の木の形の配列、光栄の最後から数えて第一です。
正解は線分樹+圧位ですか?
コード:
お互いに、phi、なくなりました
60本の木の形の配列、光栄の最後から数えて第一です。
正解は線分樹+圧位ですか?
コード:
#include<bits/stdc++.h>
#define lw(x) (x&-x)
using namespace std;
const int maxn=1e5+5;
const int M=19961993;
struct BIT{
int d[maxn];
void updata(int x,int f){while(x<maxn)d[x]+=f,x+=lw(x);}
int get(int x){int o=0;while(x)o+=d[x],x-=lw(x);return o;}
}T[61];
int getint(){
int res=0;char c=getchar();
while(!isdigit(c))c=getchar();
while(isdigit(c))res=res*10+c-'0',c=getchar();
return res;
}
int p[300],a[maxn][61];
short indx[300];
void get_p(){
static bool notp[300];
for(int i=2;i<300;i++){
if(!notp[i]){p[++p[0]]=i;indx[i]=p[0];}
for(int j=1;j<=p[0]&&i*p[j]<300;j++){
notp[i*p[j]]=1;
if(i%p[j]==0)break;
}
}
}
typedef long long LL;
int pw(int x,int k){
int ans=1;
for(;k;k>>=1){
if(k&1)ans=(LL)ans*x%M;
x=(LL)x*x%M;
}return ans;
}
int main(){
get_p();
for(int i=1;i<=1e5;i++)a[i][2]=1,T[2].updata(i,1);
int n=getint();
while(n--){
if(!getint()){
int ans=1,l=getint(),r=getint();
for(int i=1;i<=60;i++){
int mi=T[i].get(r)-T[i].get(l-1);
if(!mi)continue;
ans=(LL)ans*pw(p[i],mi-1)%M*(p[i]-1)%M;
}printf("%d
",ans);
}else{
int ps=getint(),x=getint();
for(int i=1;i<=60;i++){
int cnt=0;
while(x%p[i]==0)cnt++,x/=p[i];
T[i].updata(ps,-a[ps][i]);
T[i].updata(ps,a[ps][i]=cnt);
}
}
}
return 0;
}