Lucas定理
当(p)是质数时，有((^n_m)equiv(^{n/p}_{m/p}) * (^{n\%p}_{m\%p}) pmod{p})
狄利克雷卷积
定义：((f*g)(n)=sum_{d|n}f(d)g(frac{n}{d}))
然后满足交换律，结合律，分配律
单位元：(e=[n=1])，即(f*e=e*f=f)
逆元：对于每一个(f(1) e0)的函数(f)，存在逆元(g)使得(f*g=e)
那么(g(n))满足递推式：
(g(n)=frac{1}{f(1)}([n=1]-sum_{i|n,i
e1}f(i)g(frac{n}{i})))
Extra
定义1：((foplus g)(x)=sum_{x|d}f(frac{d}{x})g(d))
那么有，((f*g)oplus h =f oplus (g oplus h))
定义2:((fcdot g)(x)=f(x)g(x))
那么当(f)是完全积性函数时，有((fcdot g)*(fcdot h)=fcdot (g*h))
常见数论函数
(1(x)=1)
(id^k(x)=x^k)
(phi(x)=sum_{i=1}^{x}[gcd(i,x)=1])
(d(x)=sum_{d|x}1)
(sigma(x)=sum_{d|x}d)
(mu：1)的逆元
其中的一些关系：
(d = 1*1)
(id = 1*phi)
(sigma=1*id=1*1*phi=d*phi)
(phi=id*mu)
(1=d*mu)
(id=sigma*mu)
莫比乌斯反演
如果(g=f*1)，则(g*mu=f)
如果(g=1oplus f),则(f=mu oplus g)
证明：(mu oplus g=mu oplus (1 oplus f)=(mu * 1)oplus f = f)
例题
[SDOI2015] 约数个数和
求(sum_{i=1}^nsum_{i=1}^md(ij))
(d(ij)=sum_{a|i}sum_{b|j}[gcd(a,b)=1])
那么，原式等于
定义：(S(n)=sum_{i=1}^nlfloorfrac{n}{i} floor)
void init() {
mu[1] = 1;
for (int i = 2; i <= 50000; i++) {
if (!np[i]) { p[++tot] = i; mu[i] = -1; }
for (int j = 1; j <= tot && p[j] * i <= 50000; j++) {
np[p[j] * i] = 1;
if (!(i % p[j])) break;
mu[p[j] * i] = -mu[i];
}
}
for (int i = 2; i <= 50000; i++) mu[i] += mu[i - 1];
for (int i = 1; i <= 50000; i++)
for (int l = 1, r; l <= i; l = r + 1) {
r = i / (i / l);
S[i] += (r - l + 1) * (i / l);
}
return ;
}
main() {
init();
int T;
scanf("%lld", &T);
while (T--) {
int n, m;
scanf("%lld%lld", &n, &m);
if (n > m) swap(n, m);
int ans = 0;
for (int l = 1, r; l <= n; l = r + 1) {
r = min(m / (m / l), n / (n / l));
ans += (mu[r] - mu[l - 1]) * S[n / l] * S[m / l];
}
printf("%lld
", ans);
}
return 0;
}
[SHOI2015]超能粒子炮·改
求(sum_{i=0}^{k}(^n_i))
根据(Lucas)定理
可以通过对模数相同的放在一块计算
再递归求解即可。
int Lucas(LL n, LL m) {
if (!n || !m) return 1;
return Lucas(n / P, m / P) * C[n % P][m % P] % P;
}
int f(LL n, LL k) {
if (n <= 3000 && k <= 3000) return F[n][k];
return (f(n % P, P - 1) * f(n / P, k / P - 1) % P +
f(n % P, k % P) * Lucas(n / P, k / P) % P) % P;
}
void init() {
for (int i = 0; i <= 3000; i++) C[i][0] = 1;
for (int i = 1; i <= 3000; i++)
for (int j = 1; j <= i; j++)
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % P;
for (int i = 0; i <= 3000; i++) {
F[i][0] = C[i][0];
for (int j = 1; j <= 3000; j++)
F[i][j] = (F[i][j - 1] + C[i][j]) % P;
}
return ;
}
CF1097F Alex and a TV Show
因为只关心奇偶性，我们考虑使用(bitset)维护因子集合(g(x))
操作2是异或
操作3是并
因为(g=1oplus f)
(f(x))是(x)在集合出现的次数
反演一下就是,(f=muoplus g)
void prework(int n) {
Mu.set();
for (int i = 2; i * i <= n; i++)
for (int j = 1; j * i * i <= n; j++)
Mu[i * i * j] = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j * i <= n; j++)
mu[i][j * i] = Mu[j], p[j * i][i] = 1;
}
int main() {
prework(7000);
int n, Q;
scanf("%d%d", &n, &Q);
while (Q--) {
int op, x, y, z;
scanf("%d%d%d", &op, &x, &y);
if (op == 1) S[x] = p[y];
else if (op == 2) {
scanf("%d", &z);
S[x] = S[y] ^ S[z];
}
else if (op == 3) {
scanf("%d", &z);
S[x] = S[y] & S[z];
}
else printf("%d", (mu[y] & S[x]).count() & 1);
}
return 0;
}
Luogu5176 公约数
首先，(gcd(ij,jk,ik)=frac{gcd(i,j)gcd(j,k)gcd(i,k)}{gcd(i,j,k)})
那么，
(Ans=sum_isum_jsum_k(i,j)^2(j,k)^2(i,k)^2)
(=sum_isum_jsum_k(i,j)^2(j,k)^2+sum_isum_jsum_k^2(j,k)^2(i,k)^2+sum_isum_jsum_k(i,j)^2(i,k)^2)
那么定义(F(n,m)=sum_isum_j(i,j)^2)，则(Ans=F(n,m)*p+F(n,p)*m+F(m,p)*n)
现在问题就是求(F(n,m))
(F(n,m)=sum_isum_j(i,j)^2)
(=sum_{d=1}^nd^2sum_{i=1}^{lfloorfrac{n}{d}
floor}sum_{j=1}^{lfloorfrac{m}{d}
floor}[gcd(i,j)=1])
(=sum_{d=1}^nd^2sum_{i=1}^{lfloorfrac{n}{d}
floor}sum_{j=1}^{lfloorfrac{m}{d}
floor}sum_{k|i,k|j}mu(k))
(=sum_{d=1}^nd^2sum_{k=1}^{lfloorfrac{n}{d}
floor}mu(k)lfloorfrac{n}{kd}
floorlfloorfrac{m}{kd}
floor)
到这一步已经可以做到(O(n ^ frac{3}{4}))
考虑优化，
设(T=kd)
原式(=sum_{T=1}^nlfloorfrac{n}{T}
floorlfloorfrac{m}{T}
floorsum_{d|T}d^2mu(frac{T}{d}))
可以发现后面就是(id^2*mu)
显然是个积性函数，考虑线性筛
(f(p^0)=1)
(f(p)=p^2-1)
(f(p^k)=(p^2-1)p^{2(k-1)}=p^2f(p^{k-1}))