## 莫比乌斯反演与容斥原理

mobius_and_inclusion_exclusion_principle

## 【SPOJ DIVCNT2】Counting Divisors (square)

### 解题报告

spoj_divcnt2_solution

## 【BZOJ 2986】Non-Squarefree Numbers

### 解题报告

prefix_sum_of_mobius_function

## 【BZOJ 3994】[SDOI2015] 约数个数和

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 50000+9;

int n,m,tot,pri[N],mu[N],d[N],sum[N],f[N];
bool vis[N]; LL vout;

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void prework() {
mu[1] = 1;
for (int i=2;i<N;i++) {
if (!vis[i]) pri[++tot] = i, mu[i] = -1;
for (int j=1;j<=tot&&pri[j]*i<N;j++) {
vis[i*pri[j]] = 1;
if (i % pri[j]) mu[i*pri[j]] = -mu[i];
else {mu[i*pri[j]] = 0; break;}
}
}
for (int i=1;i<N;i++)
for (int j=i;j<N;j+=i)
d[j]++;
for (int i=1;i<N;i++) {
f[i] = f[i-1] + d[i];
sum[i] = sum[i-1] + mu[i];
}
}

int main() {
prework();
if (m > n) swap(n, m);
for (int l=1,r;l<=m;l=r+1) {
r = min(n / (n / l), m / (m / l));
vout += (LL)(sum[r] - sum[l-1]) * f[n/l] * f[m/l];
}
printf("%lld\n",vout);
}
return 0;
}


## 【BZOJ 3025】[Balkan2003] Farey数列

#include<bits/stdc++.h>
#define LL long long
#define LD long double
using namespace std;

const int N = 100000+9;
const LL EPS = 1e10;

int pri[N],tot,n,cnt,mu[N];
LL f[N],K,vx,vy;
bool vis[N];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

inline void Get_Mu() {
mu[1] = 1;
for (int i=2;i<=n;i++) {
if (!vis[i]) pri[++tot] = i, mu[i] = -1;
for (int j=1;j<=tot&&i*pri[j]<=n;j++) {
vis[i*pri[j]] = 1;
if (i%pri[j]) mu[i*pri[j]] = -mu[i];
else {mu[i*pri[j]] = 0; break;}
}
}
}

inline LL Get(LL w) {
for (int i=1;i<=n;i++) f[i] = i * w / EPS;
for (int i=2;i<=n;i++) f[i] += f[i-1];

LL ret = 0, sta;
for (int i=1;i<=n;i++) {
sta = (LL)EPS * n / (w * i);
ret += f[min(n/(LL)i, sta)] * mu[i];
if (sta < n/i) ret += (n/i) * (n/i - sta) * mu[i];
}
return ret;
}

inline void Get_Ans(LL w) {
for (int y=1,x;y<=n;y++) {
x = min((LL)n, w * y / EPS);
if (x && (vx * y < vy * x || !vx))
vx = x, vy = y;
}
printf("%lld %lld\n", vx, vy);
}

int main(){
cin>>n>>K;
Get_Mu();

LL l=1, r=(LL)n*EPS, mid, ret;
while (l <= r) {
mid = l + r >> 1;
if (Get(mid) <= K) ret = mid, l = mid + 1;
else  r = mid - 1;
}
Get_Ans(ret);
return 0;
}


## 【SPOJ 7001】VLATTICE

#include<iostream>
#include<cstdio>
#include<bitset>
#define LL long long
using namespace std;

const int MAXN = 1000000+9;
const int MX = 1000000;

int pri[MAXN],tot,mu[MAXN];
bitset<MAXN> tag;

inline void Get_mu(){
mu[1] = 1;
for (int i=2;i<=MX;i++) {
if (!tag[i]) pri[++tot] = i, mu[i] = -1;
for (int j=1;j<=tot && i*pri[j]<=MX;j++){
tag[i*pri[j]] = 1;
if (i % pri[j]) mu[i*pri[j]] = -mu[i];
else {mu[i*pri[j]]=0; break;}
}
}
for (int i=1;i<=MX;i++) mu[i] += mu[i-1];
}

int main(){
Get_mu(); int n,T,tmp; cin>>T;
while (T--) {
scanf("%d",&n); LL vout = 0;
for (int i=1;i<=n;i=tmp+1){
tmp = n/(n/i);
vout += (LL)(mu[tmp]-mu[i-1])*(n/i)*(n/i);
} vout = vout*3+3;
for (int i=1;i<=n;i=tmp+1){
tmp = n/(n/i);
vout += (LL)(mu[tmp]-mu[i-1])*(n/i)*(n/i)*(n/i);
}
printf("%lld\n",vout);
}
return 0;
}


—– UPD 2016.9.21 —–

$$\sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {\sum\limits_{k = 1}^n {[\gcd (i,j,k) = 1] = } } } \sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {\sum\limits_{k = 1}^n {\sum\limits_{d|\gcd (i,j,k)} {\mu (d)} = \sum\limits_{d = 1}^n {\mu (d) \cdot {{\left\lfloor {\frac{n}{d}} \right\rfloor }^3}} } } }$$

## 【BZOJ 2820】YY的GCD

#include<iostream>
#include<cstdio>
#include<bitset>
#define LL long long
using namespace std;

const int MAXN = 10000000+9;
const int MX = 10000000;

int pri[MAXN],tot,fuc[MAXN],mu[MAXN];
bitset<MAXN> tag;

inline void Get_Fuc(){
fuc[1] = 0;
for (int i=2;i<=MX;i++){
if (!tag[i]) pri[++tot] = i, fuc[i] = 1, mu[i] = -1;
for (int j=1;j<=tot && i*pri[j]<=MX;j++){
tag[i*pri[j]] = 1;
if (i % pri[j]) fuc[i*pri[j]] = -fuc[i] + mu[i], mu[i*pri[j]] = -mu[i];
else {fuc[i*pri[j]] = mu[i]; mu[i] = 0; break;}
}
}
for (int i=2;i<=MX;i++) fuc[i] += fuc[i-1];
}

int main(){
Get_Fuc(); int T; cin>>T;
while (T--) { LL vout = 0;
int n,m,tmp; scanf("%d%d",&n,&m);
if (n > m) swap(n,m);
for (int i=1;i<=n;i=tmp+1){
tmp = min(n/(n/i),m/(m/i));
vout += (LL)(fuc[tmp]-fuc[i-1])*(n/i)*(m/i);
}
printf("%lld\n",vout);
}
return 0;
}


## 【BZOJ 2705】[SDOI2012] Longge的问题

ps:hht告诉我们，除数函数可以线筛，然而一脸懵逼QAQ

DFS-version：https://oi.abcdabcd987.com/eight-gcd-problems/（我就偷懒不写啦！）
original-version:

#include<iostream>
#include<cstdio>
#include<cmath>
#define LL long long
using namespace std;

inline LL Get_Phi(LL n){
LL ret = n;
for (int i=2,lim=ceil(sqrt(n));i<=lim;i++) if (n % i == 0) {
ret = ret*(i-1)/i;
while (n % i == 0) n /= i;
}
if (n > 1) ret = ret*(n-1)/n;
return ret;
}

int main(){
LL n,vout=0; scanf("%lld",&n);
for (int i=1,lim=ceil(sqrt(n));i<=lim;i++) if (n%i == 0) {
vout += (LL)i*Get_Phi(n/i);
if (i*i < n) vout += (LL)(n/i)*Get_Phi(i);
}
printf("%lld\n",vout);
return 0;
}


—————————— UPD 2017.4.8 ——————————

## 【BZOJ 2190】[SDOI2008] 仪仗队

#include<iostream>
#include<cstdio>
#include<bitset>
using namespace std;

const int MAXN = 40000+9;

int n,pri[MAXN],tot,phi[MAXN];
bitset<MAXN> tag;

inline void Get_Phi(){
phi[1] = 1;
for (int i=2;i<=n;i++){
if (!tag[i]) pri[++tot] = i, phi[i] = i-1;
for (int j=1;j<=tot && pri[j]*i<=n;j++) {
tag[i*pri[j]] = 1;
if (i % pri[j]) phi[i*pri[j]] = phi[i]*(pri[j]-1);
else {phi[i*pri[j]] = phi[i]*pri[j]; break;}
}
}
for (int i=2;i<=n;i++) phi[i] += phi[i-1];
}

int main(){
scanf("%d",&n); n-=1;
Get_Phi();
printf("%d\n",phi[n]*2-1+2);
return 0;
}


## 【BZOJ 2818】Gcd

#include<iostream>
#include<cstdio>
#include<bitset>
#define LL long long
using namespace std;

const int MAXN = 10000000+9;

int pri[MAXN],tot,mu[MAXN],n;
bitset<MAXN> tag;

inline void Get_mu(){
mu[1] = 1;
for (int i=2;i<=n;i++){
if (!tag[i]) pri[++tot] = i, mu[i] = -1;
for (int j=1;j<=tot && pri[j]*i <= n;j++){
tag[i*pri[j]] = 1;
if (i % pri[j]) mu[i*pri[j]] = -mu[i];
else {mu[i*pri[j]] = 0; break;}
}
}
for (int i=1;i<=n;i++) mu[i] += mu[i-1];
}

int main(){
scanf("%d",&n); Get_mu(); LL vout = 0;
for (int j=1;j<=tot && pri[j] <= n;j++) {
int k = pri[j], a=n/k;
for (int i=1,tmp;i<=a;i=tmp+1)
tmp = a/(a/i),
vout += (LL)(mu[tmp]-mu[i-1])*(a/i)*(a/i);
}
printf("%lld\n",vout);
return 0;
}


#include<iostream>
#include<cstdio>
#include<bitset>
#define LL long long
using namespace std;

const int MAXN = 10000000+9;

int pri[MAXN],tot,n;
LL phi[MAXN],vout=0;
bitset<MAXN> tag;

inline void Get_Phi(){
phi[1] = 1;
for (int i=2;i<=n;i++){
if (!tag[i]) pri[++tot] = i, phi[i] = i-1;
for (int j=1;j<=tot && pri[j]*i<=n;j++){
tag[pri[j]*i] = 1;
if (i % pri[j]) phi[i*pri[j]] = phi[i]*(pri[j]-1);
else {phi[i*pri[j]] = phi[i]*pri[j]; break;}
}
}
for (int i=1;i<=n;i++) phi[i] += phi[i-1];
}

int main(){
scanf("%d",&n); Get_Phi();
for (int i=1;i<=tot && pri[i] <= n;i++)
vout += phi[n/pri[i]]*2 - 1;
printf("%lld\n",vout);
return 0;
}