数论总结（持续更新）

1.gcd相关问题

1）gcd的组合问题

例1：n个数中i个数gcd为k的集合数目——O(n*logn)

令F[k]=上述k改为k的倍数的方法数，F[K]=C(beinum[k],i)

f[k]=F[k]-f[2*k]-f[3*k]-…

例2：n个数中若干个数gcd为k的集合数目——O(n*logn)

F[k]=2^(beinum[k])-1

f[k]=F[k]-f[2*k]-f[3*k]-…

例3：gcd为k时再乘上一个权值G[i,k]，权值大小与选取的数字数目i和k有关——O(n*logn)

F[k]= ∑beinum[k]i=1C(beinum[k],i)∗G[i,k] ，对于k从1到n求和过程复杂度为O(n*logn)

f[k]=F[k]-f[2*k]-f[3*k]-…

例4：n个数中k个数gcd为1的集合个数——O(n*logn)

ans= ∑maxnumi=1u[i]∗C(beinum[i],k)

该表示方法支持点更新操作。去除/添加一个数可以在O(sqrt(numsize))内更新答案。因为一个数的因子数目不超过O(sqrt(numsize))

2）连续区间的gcd问题

1）记录（pre,l,r,x）对应的所有区间：以第r个元素结尾，左端点位于[pre,l]之间，gcd为x的区间

构造原理：以r结尾的gcd值之间是互为约数关系，每次不同的gcd至少舍去一个质因子，一个数最多有logn个质因子，因此对于每个r结尾对应的四元组数目不超过log(maxn)个，总的四元组数目不超过n*logn个

3.gcd运算问题

1) ∑ni=1∑nj=1(gcd(i,j)==1)∗f[i]∗f[j] 可以通过莫比乌斯代换变成 ∑nd=1u[d]∗(∑n/di=1f[i∗d])2

2)在出现两个无关变量的乘积p*q时，可以尝试令T=p*q，得到整除关系p|T和q|T,然后希望得到积性函数可以线性预处理

2.位运算问题

2.1异或问题

1）异或相关性质

(2k∗a)⊕(2k∗b)=2k∗(a⊕b)

(2k∗a+1)⊕(2k∗b)=2k∗(a⊕b)+1

(2k∗a+1)⊕(2k∗b+1)=2k∗(a⊕b)

2的幂次加1的异或值可以化简，因此可以通过奇偶分类讨论产生2*k和2*k+1的形式

2)异或求和问题

求解方法：逐位求和

2.2或问题

或运算具有包含性质，即a|b|c一定包含a|b的所有位，因此该运算最多得到 logn 个不同的数字

该思想与连续区间的gcd类似，最多出现logn个不同的gcd