NC22599. Rinne Loves Sequence
描述
输入描述
第一行一个整数 N，表示总的操作次数。
接下来 N 行，每行二个整数 opt,x。
若 opt=1，则表示插入 x；
若 opt=2，则表示删除 x；
若 $opt=3$，则表示询问，此时应忽略 x。
输出描述
对于每一个询问，一行输出一个非负整数表示答案。
示例1
输入:
12 1 1 3 0 1 2 3 0 1 3 3 0 1 4 3 0 1 6 3 0 2 1 3 0
输出:
0 1 3 5 6 2
C++11(clang++ 3.9) 解法, 执行用时: 64ms, 内存消耗: 6736K, 提交时间: 2020-03-25 23:37:09
#include<stdio.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
int n,b[510000],op,x,dt,d[20];
long long f[510000],ans;
void dfs(int now,int x,int w)
{
if(now>dt)
{
ans-=w*f[x]*(f[x]-1)/2;
if(op==1) f[x]++;
else f[x]--;
ans+=w*f[x]*(f[x]-1)/2;
return;
}
dfs(now+1,x*d[now],-w);
dfs(now+1,x,w);
}
int main()
{
scanf("%d",&n);
while(n--)
{
scanf("%d%d",&op,&x);
if(op<=2)
{
if(op==1&&b[x]) continue;
if(op==2&&!b[x]) continue;
b[x]^=1;
dt=0;
for(int i=2;i*i<=x;i++)
if(x%i==0)
{
d[++dt]=i;
while(x%i==0) x/=i;
}
if(x>1) d[++dt]=x;
dfs(1,1,1);
}
if(op==3)
printf("%lld\n",ans);
}
return 0;
}
C++14(g++5.4) 解法, 执行用时: 107ms, 内存消耗: 6568K, 提交时间: 2019-02-09 20:08:15
#include<stdio.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
int n,b[510000],op,x,dt,d[20];
long long f[510000],ans;
void dfs(int now,int x,int w){
if (now>dt){
ans-=w*f[x]*(f[x]-1)/2;
if (op==1) f[x]++;else f[x]--;
ans+=w*f[x]*(f[x]-1)/2;
return;
}
dfs(now+1,x*d[now],-w);
dfs(now+1,x,w);
}
int main(){
scanf("%d",&n);
while (n--){
scanf("%d%d",&op,&x);
if (op<=2){
if (op==1&&b[x]) continue;
if (op==2&&!b[x]) continue;
b[x]^=1;
dt=0;
for(int i=2;i*i<=x;i++) if (x%i==0){
d[++dt]=i;
while (x%i==0) x/=i;
}
if (x>1) d[++dt]=x;
dfs(1,1,1);
}
if (op==3) printf("%lld\n",ans);
}
return 0;
}