| 记录编号 |
317948 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[HEOI 2015]公约数数列 |
最终得分 |
100 |
| 用户昵称 |
 LOSER |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
4.442 s |
| 提交时间 |
2016-10-08 18:54:26 |
内存使用 |
17.46 MiB |
显示代码纯文本
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
using namespace std;
#define maxn 100010
#define maxq 1010
#define LL long long
map<LL,LL> q[maxq];
LL m,n,a[maxn],data,num[maxq];
LL GCD(LL a,LL b){return b==0?a:GCD(b,a%b);}
#define pos(x) Belong[x]
LL Xor[maxq][maxq],gcd[maxq][maxq];
LL Belong[maxn],size,L[maxq],R[maxq],sum[maxq];
void Makeblock(){
size=1ll*int(sqrt(n*1.0));
for(LL i=1;i<=n;i++){
pos(i)=(i-1)/size+1; R[pos(i)]=i; num[pos(i)]++;
if(!L[pos(i)]){
L[pos(i)]=i,data++,gcd[pos(i)][1]=a[i],Xor[pos(i)][1]=a[i];
}
else{
gcd[pos(i)][num[pos(i)]]=GCD(gcd[pos(i)][num[pos(i)]-1],a[i]);
Xor[pos(i)][num[pos(i)]]=Xor[pos(i)][num[pos(i)]-1]^a[i];
}
if(q[pos(i)].count(Xor[pos(i)][num[pos(i)]])==0)q[pos(i)][Xor[pos(i)][num[pos(i)]]]=num[pos(i)];
}
for(LL i=1;i<=data;i++)sum[i]=sum[i-1]+num[i];
}
void Update(LL x,LL y){
q[pos(x)].clear();
Xor[pos(x)][1]=a[L[pos(x)]]; gcd[pos(x)][1]=a[L[pos(x)]];
q[pos(x)][Xor[pos(x)][1]]=1;
for(LL i=L[Belong[x]]+1,cnt=2;i<=R[Belong[x]];i++,cnt++){
Xor[pos(i)][cnt]=Xor[pos(i)][cnt-1]^a[i];
gcd[pos(i)][cnt]=GCD(gcd[pos(i)][cnt-1],a[i]);
if(q[pos(i)].count(Xor[pos(i)][cnt])==0)q[pos(i)][Xor[pos(i)][cnt]]=cnt;
}
/*for(LL i=1;i<=data;i++){
for(LL j=1;j<=num[i];j++){
// printf("<%lld %lld> ",gcd[i][j],Xor[i][j]);
} printf("\n");
}*/
}
void Query(LL x){
for(LL i=1;i<=num[1];i++){
if(Xor[1][i]*gcd[1][i]==x){
printf("%lld\n",i-1);
return;
}
}
LL temp1=gcd[1][num[1]],temp2=Xor[1][num[1]];
// printf("--%lld %lld--\n",temp1,temp2);
for(LL i=2;i<=data;i++){
if(GCD(temp1,gcd[i][num[i]])==temp1){
LL temp3=x/temp1^temp2;
if(q[i].count(temp3)) {
printf("%lld\n",sum[i-1]+q[i][temp3]-1);
return;
}
}
else{
for(LL j=1;j<=num[i];j++){
LL data1=temp1,data2=temp2;
data1=GCD(data1,gcd[i][j]);
data2=data2^Xor[i][j];
// printf("--%lld %lld--\n",gcd[i][j],Xor[i][j]);
// printf("%lld %lld\n",data1,data2);
if(data1*data2==x){
printf("%lld\n",sum[i-1]+j-1);
return;
}
}
}
temp1=GCD(temp1,gcd[i][num[i]]); temp2=temp2^Xor[i][num[i]];
//printf("--%lld %lld--\n",temp1,temp2);
}
printf("no\n");
return;
}
int main(){
freopen("gcdxor.in","r",stdin); freopen("gcdxor.out","w",stdout);
scanf("%lld",&n);
for(LL i=1;i<=n;i++)scanf("%lld",&a[i]);
scanf("%lld",&m);
Makeblock();
//for(LL i=1;i<=data;i++)printf("%lld %lld %lld\n",L[i],R[i],num[i]);
//for(LL i=1;i<=n;i++)printf("%lld ",pos);
while( m-- ){
char ch[15]; scanf("%s",ch);
if(ch[0]=='M'){
LL x,y; scanf("%lld%lld",&x,&y); x++; a[x]=y;
Update(x,y);
}
else if(ch[0]=='Q'){
LL x; scanf("%lld",&x);
Query(x);
}
}
getchar(); getchar(); getchar();
//while(1);
return 0;
}
/*
10
1353600 5821200 10752000 1670400 3729600 6844320 12544000 117600 59400 640
10
MODIFY 7 20321280
QUERY 162343680
QUERY 1832232960000
MODIFY 0 92160
QUERY 1234567
QUERY 3989856000
QUERY 833018560
MODIFY 3 8600
MODIFY 5 5306112
QUERY 148900352
*/
/*
80 735600
80 25314672
40 774520
--240 16624400--
--80 735600--
--80 20786544--
--40 20825464--
*/
/*
--240 16624400--
--12544000 12544000--
80 735600
--250880 25787392--
80 25314672
--40 25793544--
40 774520
*/