積性函數
- 2021 年 2 月 11 日
- 筆記
莫比烏斯反演
莫比烏斯函數
定義: 將 \(x\) 質因子分解分解 \(x=p_{1}^{d_{1}}p_{2}^{d_{2}}p_{3}^{d_{3}}···p_{k}^{d_{k}}\).
\begin{array}{rcl}
0 & & \exists \ d_{i}\ge 2\\
1 & & x=1\\
(-1)^k & &
\end{array} \right. \]
莫比烏斯函數篩法:
int pri[N],vis[N],Mobius[N],tot;
void sieve_Mobius(int x)
{
vis[1]=Mobius[1]=1;
for(register int i=2;i<=x;i++)
{
if(!vis[i])
{
pri[++tot]=i;
Mobius[i]=-1;//質數只有一個質因子是他本身
}
for(register int j=1;j<=tot&&i*pri[j]<=x;j++)
{
vis[i*pri[j]]=1;
if(!(i%pri[j]))
{
Mobius[i*pri[j]]=0;//i*pri[j]里至少包含兩個pri[j]
break;
}
Mobius[i*pri[j]]=-Mobius[i];//積性函數直接乘
}
}
}
性質1: 定義 \(S(x)=\sum_{d\mid n}^{}\mu (d)\),則有:
1\ \ \ \ \ n=1\\
0\ \ \ \ \ n>1\\
\end{matrix}\right.\]
證明:
\(n=1\) 時，結論顯然成立。
\(n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}p_{3}^{\alpha_{3}}···p_{k}^{\alpha_{k}}\) , 在 \(n>1\) 時，\(k\ge 1\).
對於任意約數\(d=p_{1}^{\beta_{1}}p_{2}^{\beta_{2}}p_{3}^{\beta_{3}}···p_{k}^{\beta_{k}}\) , \(0\le\beta_{i}\le\alpha_{i}\).
若存在 \(\beta_{i}\ge 2\) , 則有 \(\mu(d)=0\).
那麼,若要使 \(\mu(d)\) 對 \(S(n)\) 產生影響 , 則需滿足 \(\forall \beta_{i}\in[0,1]\)
故, \(\mu(d)\) 的取值取決於 \(\beta_{i}=1\) 的數量, 容易得到:
\]
由二項式定理可知:
\]
將 \(a=-1\ ,\ \ b=1\) 代入得:
\]
證畢.
莫比烏斯反演
第一種形式
定義在正整數域的兩個函數 \(F(n)\) 和 \(f(n)\) , 若 \(F(n)=\sum_{d\mid n}^{}f(d)\) ,
則 \(f(n)=\sum_{d\mid n}{}\mu (d)F(\frac{n}{d})\).
證明:
\sum_{d\mid n}{}\mu (d)F(\frac{n}{d})&=\sum_{d\mid n}{}\mu (d)\sum_{i\mid \frac{n}{d}}{}f(i)\\
&=\sum_{i\mid n}{}f(i)\sum_{d\mid \frac{n}{i}}{}\mu (d)\\
&=\sum_{i\mid n}{}f(i)S(\frac{n}{i})\ \ \ \ \ \ \ 由上文可知，僅當i=n時S(\frac{n}{i})=1,否則S(\frac{n}{i})=0\\
&= f(n)
\end{aligned}\]
證畢.
第二種形式
若 \(F(n)=\sum_{n \mid d}{}f(d)\) , 則 \(f(n)=\sum_{n\mid d}{} \mu (\frac{d}{n})F(d)\).
證明:
\sum_{n\mid d}{} \mu (\frac{d}{n})F(d)&=\sum_{n\mid d}{}\mu (\frac{d}{n})\sum_{d\mid i}{}f(i)\\
&=\sum_{n\mid i}{}\sum_{d’\mid \frac{i}{n}}{}\mu (d’) \ \ \ \ \ \ \ 設d’=\frac{d}{n}\\
&= \sum_{n\mid i}{}S(\frac{i}{n})\\
&=f(n)
\end{aligned}\]
證畢.
題解:設
f(k)=\sum_{x=1}^{a}\sum_{y=1}^{b}\left [ k = (x,y) \right ]\]
則有
\]
由莫比烏斯反演定律可知:
f(k)&=\sum_{k\mid d}{}\mu(\frac{d}{k})F(d)\\
&=\sum_{k\mid d}{}\mu(\frac{d}{k})\lfloor\frac{a}{d}\rfloor\lfloor\frac{b}{d}\rfloor\\
&=\sum_{d’}{}\mu(d’)\lfloor\frac{a’}{d’}\rfloor\lfloor\frac{b’}{d’}\rfloor\ \ \ \ \ 設d’=\frac{d}{k},a’=\frac{a}{k},b’=\frac{b}{k}.
\end{aligned}\]
等式右邊 \(\lfloor\frac{a’}{d’}\rfloor\lfloor\frac{b’}{d’}\rfloor\) 可用整除分塊計算。
#include<bits/stdc++.h>
#define N 100005
#define LL long long
using namespace std;
int t;
LL a,b,c,d,k;
inline int qr()
{
int x=0,w=1;char ch=0;
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int pri[N],vis[N],mobius[N],sum[N],tot;
void sieve(int x)
{
mobius[1]=vis[1]=1;
for(register int i=2;i<=x;i++)
{
if(!vis[i])
{
pri[++tot]=i;
mobius[i]=-1;
}
for(register int j=1;j<=tot&&i*pri[j]<=x;j++)
{
vis[i*pri[j]]=1;
if(!(i%pri[j]))
{
mobius[i*pri[j]]=0;
break;
}
mobius[i*pri[j]]=-mobius[i];
}
}
for(register int i=1;i<=x;i++)
sum[i]=sum[i-1]+mobius[i];
}
inline LL f(int a,int b)
{
LL res=0;
a=a/k,b=b/k;
int n=min(a,b);
int l=1,r=0;
while(l<=n)
{
r=min(n,min(a/(a/l),b/(b/l)));
res+=(LL)(sum[r]-sum[l-1])*(a/l)*(b/l);
l=r+1;
}
return res;
}
int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
sieve(50005);
t=qr();
while(t--)
{
a=qr();b=qr();c=qr();d=qr();k=qr();
printf("%lld\n",f(b,d)-f(a-1,d)-f(b,c-1)+f(a-1,c-1));
}
//system("pause");
return 0;
}
