分析
对每个集合维护一个 bitset,第 $i$ 位表示 $i$ 作为因数的出现次数的奇偶性。
$1$ 操作预处理后直接赋值即可; $2$ 操作直接异或即可; $3$ 操作直接与即可。下面考虑 $4$ 操作怎么做。
设 $f(i)$ 表示 $i$ 作为因子的出现次数, $g(i)$ 表示 $i$ 的出现次数,那么有 $f(x)=\sum\limits_{x|d}g(d)$ ;莫比乌斯反演可得 $g(x)=\sum\limits_{x|d}\mu(\frac{d}{x})f(d)$ 。
维护一些 bitset ,假设叫 $Mu$ 。设 $\Mu_{i, j} (i|j)$ 表示 $\mu(\frac{j}{i})$ ,于是只要与一下,然后 $1$ 的个数就是答案了。
因为运算在模 $2$ 意义下进行,所以 $1$ 和 $-1$ 是一样的。
代码
// ===================================
// author: M_sea
// website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <bitset>
#include <cmath>
#define re register
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=100000+10;
const int L=7000+10;
int v[L],p[L],cnt=0;
int mu[L];
bitset<L> bit[N],Mu[L],S[L];
inline void sieve(int n) {
v[1]=mu[1]=1;
for (re int i=2;i<=n;++i) {
if (!v[i]) p[++cnt]=i,mu[i]=-1;
for (re int j=1;j<=cnt&&i*p[j]<=n;++j) {
v[i*p[j]]=1;
if (i%p[j]) mu[i*p[j]]=-mu[i];
else break;
}
}
for (re int i=1;i<=n;++i)
for (re int j=i;j<=n;j+=i)
S[j][i]=1,Mu[i][j]=(mu[j/i]!=0);
}
int main() {
sieve(7000);
int n=read(),Q=read();
while (Q--) {
int op=read();
if (op==1) {
int x=read(),y=read();
bit[x]=S[y];
}
else if (op==2) {
int x=read(),y=read(),z=read();
bit[x]=bit[y]^bit[z];
}
else if (op==3) {
int x=read(),y=read(),z=read();
bit[x]=bit[y]&bit[z];
}
else {
int x=read(),y=read();
printf("%d",(bit[x]&Mu[y]).count()&1);
}
}
return 0;
}
2 条评论
话说这题蒟蒻现场找找规律就a了。。。事后才有人告诉我我瞎推的系数是莫比乌斯miu函数。。。
海星