首页 > 其他分享 >莫比乌斯反演

莫比乌斯反演

时间：2023-07-13 21:37:09浏览次数：46  
标签：lfloor frac limits 乌斯 sum rfloor 反演 莫比 left

函数定义

\[\begin{aligned} \\ I(n)&=1\\ \epsilon(n)&=[n=1]\\ id(n)&=n \end{aligned} \]

卷积定义

\[(f*g)(x)=\sum\limits_{d|n}f(d)g(\dfrac{n}{d}) \]

有以下性质：

\[\begin{aligned} f*g&=g*f\\ (f*g)*h&=f*(g*h)\\ (f+g)*h&=f*h+g*h \end{aligned} \]

三个等式：

\[\begin{aligned} \mu*I=\epsilon\\ \phi*I=id\\ \mu*id=\phi \end{aligned} \]

  • 证明：

  • 第一个等式：

    我们把式子展开：\((\mu* I)(n)=\sum\limits_{d|n}\mu(d)I(\dfrac{n}{d})=\sum\limits_{d|n}\mu(d)\)，根据莫比乌斯函数的定义不难发现，我们可以认为 \(n=p_1p_2...p_m\) ，即我们只保留指数的种类而非其指数，这是因为所有带指数的式子对答案都没有贡献。我们考虑每个因子选与不选两种情况，不难发现我选奇数个因子和偶数个因子的方案数都是 \(2^{m-1}\) 次方。注意上面的讨论并不包括 \(n=1\) ，所以根据莫比乌斯函数定义，当且仅当 \(n=1\) 时，卷积值才为 \(1\) 否则为 \(0\) 。定理得证。

  • 第二个等式:

    \((\phi*I)(n)=\sum\limits_{d|n}\phi(d)I(\dfrac{n}{d})=\sum\limits_{d|n}\phi(d)\)，令 \(n=p_1^{m_1}p_2^{m_2}...p_k^{m_k}\)，我们实际上是在枚举 \(n\) 的某一个因子。根据 \(\phi(n)\) 为一个积性函数，我们可以把所有的 \(d\) 拆开，我们就可以得到 \(\sum\limits_{d|n}\phi(d)=(\sum\limits_{i_1=0}^{m_1}\phi(p_1^{i_1}))\times ...(\sum\limits_{i_k=0}^{m_k}\phi(p_k^{i_k}))\) ，不难发现 \(\sum\limits_{i_j=0}^{m_j}\phi(p_j^{i_j})=(\sum\limits_{k=1}^{m_j}p_j^{k-1})(p_j-1)=p_j^{m_j}\) ，所以得证。

  • 第三个等式：

  • 首先证明这样一个等式： \((\epsilon*f)(n)=\sum\limits_{d|n}\epsilon(d)f(\dfrac{n}{d})=\epsilon(1)f(n)=f(n)\)，所以 \(\epsilon*f=f\)，我们在第三个等式左边同时卷上一个 \(\epsilon\) ，得证。

莫比乌斯反演

\[\begin{aligned} g(n)=\sum\limits_{d|n}f(d)\Leftrightarrow f(n)=\sum\limits_{d|n}\mu(d)g(\dfrac{n}{d}) \end{aligned} \]

  • 证明：
  • 注意到上式可以写成 \(g=f*I\Leftrightarrow f=\mu*g\)，两边同时卷 \(I\) 就可以得证。

还有另一种形式：

\[\begin{aligned} g(n)=\sum\limits_{n|d}f(d)\Leftrightarrow f(n)=\sum\limits_{n|d}\mu(\dfrac{d}{n})g(d) \end{aligned} \]

例题 1

求 \(\sum\limits_{i=1}^n\sum\limits_{j=1}^mgcd(i,j)\)

技巧 \(1\)：增加枚举量。

\[\begin{aligned} \sum_{i=1}^n\sum_{j=1}^mgcd(i,j)=\sum_{i=1}^n\sum_{j=1}^mid(gcd(i,j))=\sum_{i=1}^n\sum_{j=1}^m\sum\limits_{d|gcd(i,j)}\phi(d) \end{aligned} \]

技巧 \(2\)：交换枚举顺序

\[\begin{aligned} \sum_{i=1}^n\sum_{j=1}^m\sum\limits_{d|gcd(i,j)}\phi(d)=\sum\limits_{d=1}^{\min(n,m)}\sum\limits_{i=1}^{\left\lfloor\tfrac{n}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\tfrac{m}{d}\right\rfloor}\phi(d) \end{aligned} \]

技巧 \(3\) ：分离无关变量

\[\begin{aligned} \sum\limits_{d=1}^{\min(n,m)}\sum\limits_{i=1}^{\left\lfloor\tfrac{n}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\tfrac{m}{d}\right\rfloor}\phi(d)=\sum\limits_{d=1}^{\min(n,m)}\phi(d)\sum\limits_{i=1}^{\left\lfloor\tfrac{n}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\tfrac{m}{d}\right\rfloor}1=\sum\limits_{d=1}^{\min(n,m)}\phi(d)\left\lfloor\dfrac{n}{d}\right\rfloor\left\lfloor\dfrac{m}{d}\right\rfloor \end{aligned} \]

可以在 \(O(n)\) 的复杂度内求解。

我们现在考虑这个问题，求：

\[\begin{aligned} \sum\limits_{i=1}^n\phi(i)\times\left\lfloor\dfrac{n}{i}\right\rfloor \end{aligned} \]

要求复杂度低于 \(O(n)\)。

考虑 \(\left\lfloor\dfrac{n}{i}\right\rfloor\) 怎么算，我们采用数论分块，可以在 \(O{\sqrt n}\) 的复杂度下求上面式子的值。

原理如下：

  • 把 \(i\) 分成 \(i\leq\sqrt n\) 和 \(i>\sqrt n\) 来讨论，我们发现 \(\left\lfloor\dfrac{n}{i}\right\rfloor\) 只有 \(2\sqrt n\) 个取值。

    所以如果我们把 \(i\) 取值中式子的值不变的放在一个块中，实际上只有大约 \(\sqrt n\) 个块。

  • 所以我们的主要问题是确定一个 \(i\) 找到一个 \(j\) ，使得 \(i\) 到 \(j\) 中的所有数，\(\left\lfloor\dfrac{n}{i}\right\rfloor\) 的值相同。

  • 首先可以二分，但这样复杂度不会很优秀。

  • 令 \(x=\left\lfloor\dfrac{n}{i}\right\rfloor\) ，那么发现 \(\left\lfloor\dfrac{n}{x}\right\rfloor\) 就应该等于 \(j\) 。可以这么理解，我们实际上是要找到满足 \(j\times x\leq n\) 的最大的 \(j\) 。那么我们就可以得出 \(j=\left\lfloor\dfrac{n}{x}\right\rfloor\) 的结论。

代码：

int get_ans(int n){
    int ans=0;
    for(int i=1;i<=n;){
        int n/(n/i);
        ans+=(n/i);
        i=j+1;
    }
    return ans;
}

如果是两个变量变化的话，我们可以看那个变量先发生变化，然后更新，去变化较早的，本质上是一样的。

例题

代码：

#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define int long long
#define ull unsigned long long
#define N 1000100
#define M number
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T>  inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

int phi[N],sumphi[N],prime[N],tail;
bool not_prime[N];

inline void getphi(){
    not_prime[1]=1;phi[1]=1;sumphi[1]=1;
    for(int i=2;i<=N;i++){
        if(!not_prime[i]) prime[++tail]=i,phi[i]=i-1;
        for(int j=1;j<=tail&&prime[j]*i<=N;j++){
            not_prime[prime[j]*i]=1;
            if(i%prime[j]==0){
                phi[prime[j]*i]=prime[j]*phi[i];
                break;
            }
            else phi[prime[j]*i]=phi[i]*phi[prime[j]];
        }
    }
//    for(int i=1;i<=100;i++) printf("%d ",phi[i]);
    for(int i=1;i<=N;i++) sumphi[i]=sumphi[i-1]+phi[i];
}

signed main(){
    getphi();int n;
    while(scanf("%lld",&n)){
        if(n==0) break;
        int ans=0;
        for(int i=1;i<=n;){
            int j=n/(n/i);
            ans+=(sumphi[j]-sumphi[i-1])*(n/i)*(n/i);
            i=j+1;
        }
        ans-=(1+n)*n/2;
        printf("%lld\n",ans/2);
    }
    return 0;
}

例题 2

求 \(\sum\limits_{i=1}^n\sum\limits_{j=1}^m[gcd(i,j)=1]\)

不难发现：

\[\begin{aligned} \sum_{i=1}^n\sum_{j=1}^mgcd(i,j)=\sum_{i=1}^n\sum_{j=1}^m\epsilon(gcd(i,j))=\sum_{i=1}^n\sum_{j=1}^m\sum\limits_{d|gcd(i,j)}\mu(d)=\sum\limits_{d=1}^{\min(n,m)}\mu(d)\left\lfloor\dfrac{n}{d}\right\rfloor\left\lfloor\dfrac{m}{d}\right\rfloor \end{aligned} \]

例题 3

对于 \(1\le x\le n,1\le y\le n\) ，求解 \(\sum\limits_{i=1}^n\sum\limits_{j=1}^m[gcd(i,j)\in Prime]\)。

我们有一个非常奇怪的条件，我们考虑增加枚举量，但不是用卷积的形式。

\[\begin{aligned} \sum\limits_{i=1}^n\sum\limits_{j=1}^m[gcd(i,j)\in Prime] &=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{p\in Prime}[gcd(i,j)=p]\\ &=\sum\limits_{p\in Prime}\sum\limits_{i=1}^{\left\lfloor\tfrac{n}{p}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\tfrac{m}{p}\right\rfloor}[gcd(i,j)=1] \end{aligned} \]

这就转化成了类似于例题 \(2\) 。

上式变成了：

\[\begin{aligned} \sum\limits_{p\in Prime}\sum\limits_{d=1}^{\min(\tfrac{m}{d},\tfrac{n}{d})}\mu(d)\left\lfloor\dfrac{n}{pd}\right\rfloor\left\lfloor\dfrac{m}{pd}\right\rfloor \end{aligned} \]

但是我们发现，我们还是有两重循环。

技巧 \(4\) ：换元法：对于两个变量乘起来的换掉。

令 \(x=pd\)，则上式变成：

\[\begin{aligned} \sum\limits_{x=1}^{min(n,m)}\sum\limits_{p\in Prime,p|x}\mu(\dfrac{x}{p})\times\left\lfloor\dfrac{n}{x}\right\rfloor\left\lfloor\dfrac{m}{x}\right\rfloor=\sum\limits_{x=1}^{min(n,m)}\left\lfloor\dfrac{n}{x}\right\rfloor\left\lfloor\dfrac{m}{x}\right\rfloor\times\sum\limits_{p\in Prime,p|x}\mu(\dfrac{x}{p}) \end{aligned} \]

而后面那个东西，实际上可以利用积性函数预处理出来。这个题就做完了。

关于后面这个式子预处理方法，我们有：

设 \(p_1\) 为 \(x\) 的最小素数，如果 \(p_1\) 在 \(x\) 中的出现次数出现了两次及以上，那么有： \(f(x)=\mu(\frac{x}{p_1})\) ，否则有：\(f(x)=\mu(\frac{x}{p_1})-f(\frac{x}{p_1})\)

不过其实也可以枚举素数 \(p\) 的倍数来做，但是这样复杂度不是很对，网上有人说那是埃筛的复杂度，似乎近似于 \(O(n\log\log n)\) 。这个复杂度是接近 \(O(n)\) 的 。

\(\text{upd}:\)

实测两种方法都是正确的，且线性做法比非线性快 \(1\) 秒。

下面的代码中，注释掉的是非线性做法。

链接

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<deque>
#include<cstdlib>
#include<ctime>
#define dd double
#define ld long double
#define ll long long
#define ull unsigned long long
#define N 10000101
#define M 700000
using namespace std;

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

inline int Min(int a,int b){
	return a>b?b:a;
}

int p[M],tail,mu[N],g[N],t,minfac[N];
bool vis[N];
ll ans=0;

int main(){
	mu[1]=1;minfac[1]=1;
	for(int i=2;i<=N-100;i++){
		if(!vis[i]) p[++tail]=i,mu[i]=-1,minfac[i]=i;
		for(int j=1;j<=tail&&i*p[j]<=N-100;j++){
			int v=i*p[j];
			vis[v]=1;
			minfac[i*p[j]]=p[j];
			if(i%p[j]!=0) mu[v]=mu[i]*mu[p[j]];
			else mu[v]=0;
			if(i%p[j]==0) break;
		}
	}
	// for(int i=1;i<=tail;i++)
	// 	for(int j=1;j*p[i]<=N-100;j++)
	// 		g[j*p[i]]+=mu[j];
	for(int i=2;i<=N-100;i++){
		g[i]+=mu[i/minfac[i]];
		if(i%(minfac[i]*minfac[i])!=0) g[i]=g[i]-g[i/minfac[i]];
	}
	for(int i=1;i<=N-100;i++) g[i]+=g[i-1];
	t=read();
	while(t--){
		int n,m;ans=0;
		n=read();m=read();
		for(int l=1,r=0;l<=Min(n,m);l=r+1){
			r=Min(n/(n/l),m/(m/l));
			ans+=(ll)(g[r]-g[l-1])*(ll)(n/l)*(ll)(m/l);
		}
		printf("%lld\n",ans);
	}
	
	return 0;
}

之所以有后面这个式子，是因为我们考虑所有能对 \(f\) 造成贡献的数原先有 \(p_1\) ，现在没有了，所以符号变化了。

如果 \(n=m\) ，我们有一种更优美的做法，从这里开始：

\[\begin{aligned} \sum\limits_{p\in Prime}\sum\limits_{i=1}^{\left\lfloor\tfrac{n}{p}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\tfrac{n}{p}\right\rfloor}[gcd(i,j)=1]\\ \end{aligned} \]

考虑：

\[\begin{aligned} \sum\limits_{i=1}^{\left\lfloor\tfrac{n}{p}\right\rfloor}\sum\limits_{j=1}^{i}[gcd(i,j)=1]\\ \end{aligned} \]

不难发现，如果我们把 \(i\) 固定，后面这个东西实际上就是 \(\phi(i)\) ，所以如果我们要计算这个式子：

\[\begin{aligned} \sum\limits_{i=1}^{\left\lfloor\tfrac{n}{p}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\tfrac{n}{p}\right\rfloor}[gcd(i,j)=1]\\ \end{aligned} \]

实际上就是上面这个式子乘上 \(2\) 再减去一些重复的部分，不难发现，只有 \(i=j\) 的情况被重复枚举了，但只有 \(i=j=1\) 的时候才会对答案造成贡献，所以我们直接乘 \(2\) 减 \(1\) 就可以。

例题

代码：

#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define int long long
#define ull unsigned long long
#define N 14000100
#define M number
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T>  inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

int phi[N],sumphi[N],prime[N],tail;
bool not_prime[N];

inline void getphi(int n){
    not_prime[1]=1;phi[1]=1;sumphi[1]=1;
    for(int i=2;i<=n;i++){
        if(!not_prime[i]) prime[++tail]=i,phi[i]=i-1;
        for(int j=1;j<=tail&&prime[j]*i<=n;j++){
            not_prime[prime[j]*i]=1;
            if(i%prime[j]==0){
                phi[prime[j]*i]=prime[j]*phi[i];
                break;
            }
            else phi[prime[j]*i]=phi[i]*phi[prime[j]];
        }
    for(int i=1;i<=n;i++) sumphi[i]=sumphi[i-1]+phi[i];
}

int n,ans;

signed main(){
    scanf("%lld",&n);
    getphi(n);
    for(int i=1;i<=tail;i++){
        ans+=(sumphi[n/prime[i]]*2-1);
    }
    printf("%lld\n",ans);
    return 0;
}

数论分块

定理

\[\left\lfloor\frac {\left\lfloor \frac{x}{b} \right\rfloor}{c} \right\rfloor=\left\lfloor\frac{x}{bc}\right\rfloor \]

其中 \(x\in\mathbb{R},b,c\in\mathbb{N}\)

  • 证明：设 \(x=kbc+r\)，其中 \(r\in[0,bc)\) ，我们把 \(x\) 带入左边式子可以的得到：

    \[k+\left\lfloor\frac {\left\lfloor \frac{r}{b} \right\rfloor}{c} \right\rfloor \]

    因为：

    \[0\le \left\lfloor\frac {\left\lfloor \frac{r}{b} \right\rfloor}{c} \right\rfloor\le \left\lfloor\frac {r}{bc} \right\rfloor=0 \]

    所以我们可以得到：

    \[\left\lfloor\frac {\left\lfloor \frac{r}{b} \right\rfloor}{c} \right\rfloor=k \]

    显然，右边式子也等于 \(k\)，所以结论成立。

算法讲解

其实数论分块（又被称为除法分块）是可以在 \(\sqrt n\) 的复杂度内算出：

\[\sum\limits_{i=1}^n\lfloor \frac{n}i \rfloor \]

这是因为我们注意到和式求和的部分的取值只有 \(2\sqrt n\) 中，证明这个结论只需要讨论 \(i\le \sqrt n\) 和 \(i> \sqrt n\)​ 两种情况即可。

一般的，对于：

\[\sum\limits_{i=1}^n\lfloor \frac{n}{f(i)}\rfloor \]

我们要求其值相等的左右边界，只需要让：

\[\lfloor\frac{n}{f(l)}\rfloor=\lfloor\frac{n}{f(r)}\rfloor \]

由数论分块的正确性可以得到：

\[f(r)=\left\lfloor \frac{n}{\lfloor \frac{n}{f(l)}\rfloor}\right\rfloor \]

我们求解 \(f(l)\) 并解方程解出 \(r\) 为多少即可得出数论分块区间。

例题

P2261 [CQOI2007]余数求和

我们直接推式子：

\[\begin{aligned} \sum\limits_{i=1}^nk\bmod i=\sum\limits_{i=1}^nk-\lfloor \frac ki\rfloor\times i=nk-\sum\limits_{i=1}^ni\lfloor\frac ik\rfloor \end{aligned} \]

可以应用数论分块，注意后面要特判是否等于 \(0\)。

代码：

#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N number
#define M number
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

inline ll calc(int l,int r){
    return 1ll*(r+l)*(r-l+1)/2;
}

ll ans=0,n,k;

int main(){
    read(n);read(k);
    for(int i=1;i<=n;){
        int j;
        if(k/i>0) j=k/(k/i);
        else j=n;
        j=min((ll)j,n);
        ans+=(k/i)*calc(i,j);
        i=j+1;
    }
    printf("%lld\n",n*k-ans);
    return 0;
}

代码第 \(31\) 行 \(32\) 行为特判。

CF1485C Floor and Mod

推式子：

\[\begin{aligned} \left\lfloor \frac{a}{b} \right\rfloor=a\bmod b=a-\lfloor\frac{a}{b}\rfloor\times b \Rightarrow \lfloor\frac{a}{b}\rfloor\times (b+1) =a\Rightarrow \lfloor\frac{a}{b}\rfloor=\frac{a}{b+1} \end{aligned} \]

所以我们只需要枚举 \(b\) ，同时统计有多少 \(a\) 是 \(b+1\) 的倍数，这个数应该是 \(\frac{x}{b+1}\) 。

但是需要注意的一点是，我们需要保证 \(\lfloor\frac{a}{b}\rfloor=\frac{a}{b+1}<b\) ，所以我们有 \(a<b^2+b\) ，所以上面这个式子应该变成：\(\frac{\min(x,b^2+b-1)}{b+1}\)。

我们根号分治并分开讨论，数论分块即可。复杂度为 \(O(\sqrt n)\)。

代码：

#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define int long long
#define uint unsigned int
#define ull unsigned long long
#define N number
#define M number
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

int t;
ll x,y;

inline ll calc(ll x,ll y){
    ll ans=0;ll b=1;
    for(;b*b+b-1<=x&&b<=y;b++) ans+=(b*b+b-1)/(b+1);
    for(int i=b;i<=y;){
        int j=(x/(i+1)==0)?y:(x/(x/(i+1))-1);
        j=min((ll)j,y);
        ans+=(x/(i+1))*(j-i+1);
        i=j+1;
    }
    return ans;
}

signed main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(t);
    while(t--){
        read(x);read(y);
        printf("%lld\n",calc(x,y));
    }
    return 0;
}

常用公式

最大公因数，最小公倍数

\[\begin{aligned} \sum\limits_{i=1}^n\sum\limits_{j=1}^m\text{lcm}(i,j)&=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\frac{ij}{\gcd(i,j)} \\ &=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{d|i,d|j} [\gcd(\frac id,\frac jd)=1]\frac{ij}d\\ &=\sum\limits_{d=1}^{\min(n,m)}d\sum\limits_{i=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum\limits_{j=1}^{\left\lfloor \frac{m}{d} \right\rfloor}[\gcd(i,j)=1]ij\\ \end{aligned} \]

令 \(f(n,m)=\sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i,j)=1]ij\)，那么有：

\[\begin{aligned} f(n,m)&=\sum\limits_{i=1}^n\sum\limits_{i=1}^m\epsilon(\gcd(i,j))ij\\ &=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{d|\gcd(i,j)}\mu(d)ij\\ &=\sum\limits_{d=1}^{\min(n,m)}\mu(d)d^2\sum\limits_{i=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum\limits_{j=1}^{\left\lfloor \frac{m}{d} \right\rfloor}ij\\ \end{aligned} \]

令 \(g(n,m)=\sum\limits_{i=1}^n\sum\limits_{j=1}^m ij\)，显然，我们有 \(g(n,m)=\frac{(n+1)n}{2}\frac{(m+1)m}{2}\) ，可以 \(O(1)\) 计算，所以通过处理前缀和，\(f(n,m)\) 可以在 \(O(\sqrt n+\sqrt m)\) 的时间1复杂度算出，所以原式的复杂度可以做到 \(O(n+m+\sqrt n+\sqrt m)\) 。

除数函数

  • \(\sigma_k(n)=\sum\limits_{d|n}d^k\)​​ ，令 \(id_k(n)=n^k\)​​ ，那么我们有 \(\sigma_k=id_k*I\)​​

  • \(\sigma_0(xy)=\sum\limits_{i|x}\sum\limits_{j|y}[\gcd(i,j)=1]\)

证明：我们考虑将 \(xy\)​​ 的每一个因子都与互质的 \(i,j\)​​ 意义映射。设 \(xy\)​​ 的因子为 \(k\)​​ ，设把 \(k\)​​ 唯一分解之后得到的式子为 \(\prod\limits_{i=1}^mp_i^{\alpha_i}\)​​​ 我们考虑每一个质数，设当前的质数为 \(p\)​​ ，设这个质数在 \(k\)​​ 中的指数为 \(\alpha\)​​ ，设在 \(x\)​​ 中的指数为 \(a\)​​ 设在 \(y\)​​ 中的指数为 \(b\)​​​ 。我们规定，如果 \(\alpha \le a\)​ ，那么令从 \(x\)​ 中拿取 \(p^{\alpha}\)​ ，否则就从 \(y\)​ 中拿取 \(p^{\alpha -a}\)​ 次方。这样，从 \(x\)​​ 中拿出来数就与从 \(y\)​​ 中拿出来的数互质。同时每一对互质的数，都可以映射到这么一个因子上。所以等式成立。证毕。

  • 除数函数是积性函数。

证明：如果 \(x,y\) 互质，那么 \(xy\) 的一个因子 \(k\) ，\(k\) 一定可以分解成两个数，这两个数互质。也就是说，\(k\) 一部分来自 \(x\) ，一部分来自 \(y\)​ 。证毕。

上面这个积性函数的性质，揭示我们除数函数也是可以线性筛的。不过我们有计算一些特殊除数函数前缀和更快的做法。

  • \(\sum\limits_{i=1}^n\sigma_0(i)=\sum\limits_{j=1}^n\left\lfloor \frac{n}{j} \right\rfloor\)​

证明：推导可知

\[\begin{aligned} \sum\limits_{i=1}^n\sigma_0(i)=\sum\limits_{i=1}^n\sum\limits_{j=1}^i[j|i]=\sum\limits_{j=1}^n\sum\limits_{i=1}^{\left\lfloor \frac{n}{j} \right\rfloor}1=\sum\limits_{j=1}^n \left\lfloor \frac{n}{j} \right\rfloor \end{aligned} \]

  • \(\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sigma_0(ij)=\sum\limits_{d=1}^{\min(n,m)}\mu(d)(\sum\limits_{x=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\left\lfloor \frac{n}{xd} \right\rfloor)(\sum\limits_{y=1}^{\left\lfloor \frac{m}{d} \right\rfloor}\left\lfloor \frac{m}{yd} \right\rfloor)\)​

证明：

\[\begin{aligned} \sum\limits_{i=1}^n\sum\limits_{j=1}^m\sigma_0(ij)&=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{x|i}\sum\limits_{y|j}\epsilon(\gcd(x,y))\\ &=\sum\limits_{x=1}^n\sum\limits_{y=1}^m \epsilon(\gcd(x,y)) \sum\limits_{i=1}^{\left\lfloor \frac{n}{x} \right\rfloor}\sum\limits_{j=1}^{\left\lfloor \frac{m}{y} \right\rfloor}1\\ &=\sum\limits_{x=1}^n\sum\limits_{y=1}^m\sum\limits_{d|\gcd(x,y)}\mu(d)\left\lfloor \frac{n}{x} \right\rfloor\left\lfloor \frac{m}{y} \right\rfloor\\ &=\sum\limits_{d=1}^{\min(n,m)}\sum\limits_{x=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum\limits_{y=1}^{\left\lfloor \frac{m}{d} \right\rfloor}\mu(d)\left\lfloor \frac{n}{xd} \right\rfloor\left\lfloor \frac{m}{yd} \right\rfloor\\ &=\sum\limits_{d=1}^{\min(n,m)}\mu(d)(\sum\limits_{x=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\left\lfloor \frac{n}{xd} \right\rfloor)(\sum\limits_{y=1}^{\left\lfloor \frac{m}{d} \right\rfloor}\left\lfloor \frac{m}{yd} \right\rfloor) \end{aligned} \]

  • \(\sigma_1(xy)=\sum\limits_{i|x}\sum\limits_{j|y}\frac{jx}{i}[\gcd(i,j)=1]\)​​

证明：同样还是构造一一对应来证明，构造方法和上面证明 \(2.1.2.2\) 相同，设：

\[\begin{aligned} x=\prod\limits_{i=1}^np_i^{\alpha_i},y=\prod\limits_{j=1}^np_j^{\beta_j}\\ i=\prod\limits_{j=1}^kp_{i_j}^{a_{i_j}},j=\prod_{i=1}^{n-k}p_{j_i}^{a_{j_i}} \end{aligned} \]

我们看 \(\frac{jx}i\)​ 的值表示出来是多少，我们发现这个值是：

\[\prod\limits_{j=1}^k p_{i_j}^{\alpha_{i_j}-a_{i_j}}\times \prod\limits_{i=1}^{n-k}p_{j_i}^{\alpha_{j_i}+a_{j_i}} \]

这个 \(i,j\)​ 对应的因子是 \(\prod_{j=1}^kp_{i_j}^{a_{i_j}}\prod_{p_{j_i}}^{n-k}p_{j_i}^{\alpha_{j_i}+a_{j_i}}\)​，不难发现，这个因子与上面相比，右边相同，左边相乘是 \(x\)​​​ ，所以这两个因子是一一对应的。显然这个式子是正确的。

  • \(\sum\limits_{i=1}^n\sigma_1(i)=\sum\limits_{i=1}^ni\left\lfloor \frac{n}{i} \right\rfloor\)

证明：

\[\begin{aligned} \sum\limits_{i=1}^n\sigma_1(i)=\sum\limits_{i=1}^n\sum\limits_{j=1}^ij[j|i]=\sum\limits_{j=1}^n\sum\limits_{i=1}^{\left\lfloor \frac{n}{j} \right\rfloor}j=\sum\limits_{i=1}^nj\left\lfloor \frac{n}{j} \right\rfloor \end{aligned} \]

  • \(\sum\limits_{i=1}^n\sum\limits_{j=1}^n\sigma_1(ij)=\sum\limits_{d=1}^n\mu(d)d(\sum\limits_{i=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sigma_1(i))^2\)​

证明：

\[\begin{aligned} \sum\limits_{i=1}^n\sum\limits_{j=1}^n\sigma_1(ij)&=\sum\limits_{i=1}^n\sum\limits_{j=1}^n\sum\limits_{x|i}\sum\limits_{y|j}\frac{jx}{y}[\gcd(x,y)=1]\\ &=\sum\limits_{x=1}^{n}\sum\limits_{y=1}^n\sum\limits_{i=1}^{\left\lfloor \frac{n}{x} \right\rfloor}\sum\limits_{j=1}^{\left\lfloor \frac{n}{y} \right\rfloor}jx\times \epsilon(\gcd(x,y))\\ &=\sum\limits_{d=1}^n\mu(d)d \sum\limits_{x=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum\limits_{y=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum\limits_{i=1}^{\left\lfloor \frac{n}{xd} \right\rfloor}\sum\limits_{j=1}^{\left\lfloor \frac{n}{yd} \right\rfloor}jx\\ &=\sum\limits_{d=1}^{n}\mu(d)d\sum\limits_{x=1}^{\left\lfloor \frac{n}{d} \right\rfloor}x\left\lfloor \frac{n}{xd} \right\rfloor\sum\limits_{y=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum\limits_{j=1}^{\left\lfloor \frac{n}{yd} \right\rfloor}j\\ &=\sum\limits_{d=1}^{n}\mu(d)d\sum\limits_{x=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sigma_1(x)\sum\limits_{y=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sigma_1(y)\\ &=\sum\limits_{d=1}^{n}\mu(d)d(\sum\limits_{i=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sigma_1(i))^2 \end{aligned} \]

  • \(\sum\limits_{i=1}^n\mu^2(i)=\sum\limits_{i=1}^{\sqrt n}\mu(i)\times\left\lfloor \frac{n}{i^2} \right\rfloor\)

这个公式需要构造来证明，具体证明过程请参照例题。

  • \(\sum\limits_{i=1}^n\mu^2(i)\left\lfloor \sqrt{\frac{n}{i}} \right\rfloor\)​​

这个东西的证明和上面类似，我们同样考虑构造。考虑 \(1\) 到 \(n\) 内所有不能被完全平方数整除的数组成的集合 \(P\) ，那么 \(1\) 到 \(n\) 内的每一个数都可以表示成 \(xy^2\) 的形式，其中 \(x\in P,y\le \sqrt{\frac nx}\)，上面的式子其实等价于 \(\sum\limits_{p\in P}\left\lfloor \sqrt{\frac{n}{i}} \right\rfloor\)​，根据 \(y\) 的取值范围，不难发现这个式子的正确性。

  • \(\sum\limits_{i=1}^n\sum\limits_{j=1}^n[\gcd(i,j)=1]=\sum\limits_{d=1}^n\mu(d)\left\lfloor \frac{n}{d} \right\rfloor=2S_{\phi}(\left\lfloor \frac{n}{d} \right\rfloor)-1\)

证明：

这里只证明后面的那个式子。

设 \(f(n)=\sum\limits_{i=1}^n\sum\limits_{j=1}^n[\gcd(i,j)=1],g(n)=\sum\limits_{i=1}^n\sum\limits_{j=1}^i[\gcd(i,j)=1]\)，那么 \(g(n)=S_{\phi}(i)\)，那么容易验证有：\(f(n)=2g(n)-1\) ，减 \(1\) 是因为 \((1,1)\) 被算重了。

  • \(\prod\limits_{i=1}^n\prod\limits_{j=1}^n\gcd^2(i,j)=(\prod\limits_{i=1}^nd^{S_{\phi}(\left\lfloor \frac{n}{d} \right\rfloor)})\)

证明：

\[\begin{aligned} \prod\limits_{i=1}^n\prod\limits_{j=1}^n\gcd{^2}(i,j)&=\prod\limits_{i=1}^nd^{\sum\limits_{i=1}^n\sum\limits_{j=1}^n[\gcd(i,j)=d]}\\ &=\prod\limits_{i=1}^nd^{\sum\limits_{i=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum\limits_{j=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\gcd(i,j)=1} \end{aligned} \]

故该公式成立。

例题

洛谷P4318

不难发现，答案具有可二分性。我们规定，如果一个数不能被完全平方数整除，则称其合法，否则称其不合法。那么 \(n\) 以内的合法的数一共有多少呢？不难发现，答案应该是：

\[\sum\limits_{i=1}^n\mu^2(i) \]

即为 \(1\) 到 \(n\) 中所有 \(\mu(x)\) 不为 \(0\) 的数。

我们考虑用容斥来计算这个东西，不难发现这个东西其实也是可以这样计算的：

含 \(0\) 个质数的平方的倍数减去含 \(1\) 个质数的平方的倍数加上含 \(2\) 个质数平方的倍数......，考虑莫比乌斯函数的定义，我们发现上面这个式子其实也是：

\[\sum\limits_{i=1}^{i\times i\le n}\mu(i)\times\left\lfloor \frac{n}{i^2} \right\rfloor \]

所以我们就可以二分这个答案，然后在 \(O(\sqrt n)\) 的时间复杂度内判断合不合法。

代码：

#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N 60010
#define M number
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

int Prime[N],tail,Mu[N];
bool NotPrime[N];

inline void PreWork(int n){
    NotPrime[1]=1;Mu[1]=1;
    for(int i=2;i<=n;i++){
        if(!NotPrime[i]) Prime[++tail]=i,Mu[i]=-1;
        for(int j=1,k;j<=tail&&(k=i*Prime[j])<=n;j++){
            NotPrime[k]=1;
            if(i%Prime[j]==0) break;
            else Mu[k]=-Mu[i];
        }
    }
}

int t;

inline bool Check(int mid,int k){
    int res=0;
    for(ll i=1;i*i<=mid;i++){
        res=res+Mu[i]*(mid/(i*i));
    }
    return res>=k;
}

int main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    PreWork(60000);
    read(t);
    while(t--){
        ll k;read(k);
        ll l=k,r=2*k;
        while(l<r){
            // cout<<"l"<<" "<<l<<endl;

            int mid=(l+r)>>1;
            if(Check(mid,k)) r=mid;
            else l=mid+1;
        }
        printf("%lld\n",l);
    }
}

SP5971 LCMSUM - LCM Sum

要求计算 \(\sum_{i=1}^nlcm(i,n)\) ，我们尝试化简这个东西：

\[\begin{aligned} \sum\limits_{i=1}^nlcm(i,n)=\sum\limits_{i=1}^n\frac{in}{\gcd(i,n)}&=\sum\limits_{i=1}^n\sum\limits_{d|i,d|n}[\gcd(\frac di,\frac nd)=1]\times \frac{in}{d}\\ &=\sum\limits_{d|n}\sum\limits_{i=1}^{\left\lfloor \frac{n}{d} \right\rfloor}in[\gcd(i,\frac nd)=1] \end{aligned} \]

我们令 \(g(x)=\sum\limits_{i=1}^x[\gcd(i,x)=1]\times i\) 即在 \(1\) 到 \(x\) 总所有与 \(x\) 互质的数的个数，因为 \(\gcd(i,n)=1\Leftrightarrow\gcd(n-i,i)\) ，所以互质的数总是两两一对，且和为 \(n\) 。

所以这个和应该是 \(\frac{\phi(x)x}{2}\)。

所以上面那个式子可以化简为：

\[\begin{aligned} n\sum\limits_{d|n}\frac{\phi(d)d}{2} \end{aligned} \]

我们可以用 \(n\log n\) 的时间复杂度完成这个事情。

注：这个地方有一点不太严谨，当 \(d=1\) 的时候注意 \(g(1)=1\)，这个是个特殊的。

#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N 1000100
#define M number
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

int Prime[N],tail,Phi[N];
ll g[N],f[N];
bool NotPrime[N];

inline void PreWork(int n){
    NotPrime[1]=1;Phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!NotPrime[i]) Prime[++tail]=i,Phi[i]=i-1;
        for(int j=1,k;j<=tail&&(k=i*Prime[j])<=n;j++){
            NotPrime[k]=1;
            if(i%Prime[j]==0){
                Phi[k]=Phi[i]*Prime[j];break;
            }
            else Phi[k]=Phi[i]*Phi[Prime[j]];
        }
    }
    // for(int i=1;i<=5;i++) printf("%d ",Phi[i]);puts("");
    g[1]=1;
    for(int i=2;i<=n;i++) g[i]=1ll*Phi[i]*i/2;
    // for(int i=1;i<=5;i++) printf("%lld ",g[i]);puts("");
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j+=i) f[j]+=g[i];
    for(int i=1;i<=n;i++) f[i]*=i;
}

int t,n;

int main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    PreWork(1000000);
    read(t);
    while(t--){
        read(n);printf("%lld\n",f[n]);
    }
}//

P3768 简单的数学题

首先我们尝试化简式子：

\[\begin{aligned} \sum\limits_{i=1}^n\sum\limits_{j=1}^nij\gcd(i,j)&=\sum\limits_{k=1}^n\sum\limits_{k|i,i\le n}\sum\limits_{k|j,j\le n}ijk[\gcd(\left\lfloor \frac{k}{i} \right\rfloor,\left\lfloor \frac{k}{j} \right\rfloor)=1]\\ &=\sum\limits_{k=1}^n\sum\limits_{i=1}^{\left\lfloor \frac{n}{k} \right\rfloor}\sum\limits_{j=1}^{\left\lfloor \frac{n}{k} \right\rfloor}ijk^3[\gcd(i,j)=1] \end{aligned} \]

令 \(g(n)=\sum_{i=1}^n\sum_{j=1}^nij[\gcd(i,j)=1]\)，我们可以得到：

\[\begin{aligned} g(n)=\sum\limits_{i=1}^ni\sum\limits_{j=1}^nj[\gcd(i,j)=1]=[n\ge 1]+\sum\limits_{i=2}^n\frac{\phi(i)i}{2} \end{aligned} \]

所以原来的式子我们可以化简为：

\[\begin{aligned} \sum\limits_{k=1}^nk^3g(\left\lfloor \frac{n}{k} \right\rfloor) \end{aligned} \]

由于 \(n\) 是 \(1e9\) 级别的，所以我们可以用杜教筛筛一下 \(g(n)\) 。然后用整除分块。因为杜教筛也是整除分块计算的，所以杜教筛外面套一个整除分块没有问题。

关于除数函数一些定理的其它证明方式

在上面的内容中，我们构造的方式推导了 \(\sigma_0(ij)\) 和 \(\sum\sum\sigma_1(ij)\)，但其实他们也可以用代数推导的方式来推导。

\[\sigma_0(xy)=\sum\limits_{d|xy} 1=\sum\limits_{i|x}\sum\limits_{j|y}[i=\gcd(x,ij)]=\sum\limits_{i|x}\sum\limits_{j|y}[\gcd(i,j)=1] \]

其中第二步推导是因为：为了让 \(d\) 不被重复枚举，我们让 \(i\) 尽量多拿 \(d\) 中的质因子。

同理，我们有：

\[\sigma_1(xy)=\sum\limits_{d|xy} d=\sum\limits_{i|x}\sum\limits_{j|y}[i=\gcd(x,ij)]ij=\sum\limits_{i|x}\sum\limits_{j|y}[\gcd(i,j)=1]\frac{xj}{i} \]

莫比乌斯函数扩展

莫比乌斯函数非卷积形式。

对于数论函数和完全积性函数 \(t\) 且 \(t(1)=1\) ，有以下等价式子：

\[\begin{aligned} f(n)=\sum\limits_{i=1}^nt(i)g(\left\lfloor \frac{n}{i} \right\rfloor)\Leftrightarrow g(n)=\sum\limits_{i=1}^nt(i)\mu(i)f(\left\lfloor \frac{n}{i} \right\rfloor) \end{aligned} \]

  • 证明：

\[\begin{aligned} g(n)&=\sum\limits_{i=1}^nt(i)\mu(i)f(\left\lfloor \frac{n}{i} \right\rfloor)\\ &=\sum\limits_{i=1}^nt(i)\mu(i)\sum\limits_{j=1}^{\left\lfloor \frac{n}{i} \right\rfloor}t(j)g(\left\lfloor \frac{n}{ij} \right\rfloor)\\ &=\sum\limits_{d=1}^n\sum\limits_{i|d} t(i)\mu(i)t(\frac{d}{i})g(\left\lfloor \frac{n}{d} \right\rfloor)\\ &=\sum\limits_{d=1}^ng(\left\lfloor \frac{n}{d} \right\rfloor)t(d)\sum\limits_{i|d}t(i)\\ &=\sum\limits_{d=1}^ng(\left\lfloor \frac{n}{d} \right\rfloor)t(d)\epsilon(d) =g(n) \end{aligned} \]

标签：lfloor,frac,limits,乌斯,sum,rfloor,反演,莫比,left
From： https://www.cnblogs.com/HeNuclearReactor/p/17552220.html

相关文章

  • 拉格朗日反演
    前置引理首先设\(\Bbb{C}[[x]]=\{\sum\limits_{i\ge0}a_ix^i|a_i\in\Bbb{C}\},\Bbb{C}((x))=\{\sum\limits_{i\ge-N}a_ix^i|N\inZ,a_i\in\Bbb{C}\}\)有以下引理：\(f(x)\in\Bbb{C}((x)),[x^{-1}]f'(x)=0\)显然，因为没有一个幂次项求导后是\(-1\)次项。\(f(......
  • 二项式反演
    第一种形式：\[f(n)=\sum\limits_{i=0}^n\dbinom{n}i{g(i)}\Leftrightarrowg(n)=\sum\limits_{i=0}^n(-1)^{n+i}\dbinomnif(i)\]证明：\[\begin{aligned}f(n)&=\sum\limits_{i=0}^n\dbinom{n}i{g(i)}=\sum\limits_{i=0}^n\dbinomni\sum\limits_{j=0......
  • 单位根反演
    命题如下：$$\forallk\inZ,[n|k]=\frac{1}{n}\sum\limits_{i=0}{n-1}\omega_n$$证明：设$[n|k]=1$，则根据单位根性质，我们可以得到：$$\sum\limits_{i=0}{n-1}\omega_n=n$$设$[n|k]=0$，则：$$\sum\limits_{i=0}{n-1}\omega_n=\frac{\omega_n{nk}-1}{\omega_n-1}=0$$由此可知......
  • 莫比乌斯函数与反演
     莫比乌斯函数的原式是u(n)={1,n=1(-1)^r,n=p1*p2*p3*......*pr 其中p为不同的质数                       0,其他}它有两种解法，分别是欧拉筛和杜教筛下面给出欧拉筛的代码：#include<bits/stdc......
  • 莫比乌斯反演学习笔记
    狄利克雷卷积对于两个数论函数$f(x)$和$g(x)$，他们的卷积结果$h(x)$定义为$h(x)=\sum_{d|x}^{}f(d)g(\frac{x}{d})=\sum_{ab=x}^{}f(a)g(b) $即$h=f*g$满足交换律，结合律，分配律。莫比乌斯函数 $$\mu(n)=\left\{\begin{matrix}1 &n=1\\0 &n含有平方因子\\(-1......
  • 莫比乌斯函数入门
    莫比乌斯函数入门之前遇到过很多次莫反的题，但是每次做完就忘了，云里雾里，所以写一篇来好好记忆一下，下次再忘了就回来看看。内容和OIWIKI有很大部分的重叠，但是更偏向结论和做法，同时舍弃了一些看不懂的。莫比乌斯函数定义:\[\mu(n)=\begin{cases}1&n=1\\0&n含有平方因子(......
  • 二项式反演和 Min-Max 反演小记
    二项式反演本质上是某种容斥。结论为：\[f_i=\sum_{j=0}^i(-1)^j\binom{i}{j}g_j\Leftrightarrowg_i=\sum_{j=0}^i(-1)^j\binom{i}{j}f_j\]更常用的形式是\[f_i=\sum_{j=0}^i\binom{i}{j}g_j\Leftrightarrowg_i=\sum_{j=0}^i(-1)^{i-j}\binom{i}{j}f_j\]证明第二个......
  • [数论]数论函数/莫比乌斯反演
    数论函数/莫比乌斯反演1.1积性函数数论函数：可以认为是定义在整数上的函数。1)积性函数定义(a,b)=1,f(a,b)=f(a)f(b)2)积性函数性质对于积性函数\(f\)，是被所有\(p^e\)处的值决定的a=1,f(b)=f(1)f(b)​ \(f(60)=f(4)\timesf(15)=f(4)\timesf(3)\timesf(5......
  • fluent中的阿仑尼乌斯公式
    公式介绍阿伦尼乌斯公式（Arrheniusequation）是由瑞典的阿伦尼乌斯所创立的化学反应速率常数随温度变化关系的经验公式。公式写作$$k=AT^\betaexp(−Ea/RT)$$特别需要说明这个公式的单位：k为反应速率R为摩尔气体常数或通用气常数或普适气体常数，其值为8.314J/(mol·K)T为热力......
  • 莫比乌斯反演 学习笔记
    炫酷反演魔术！莫反会用到的具体性质证明先不写，先写题。与其说是学习笔记，不如说是简要的题解集合。不太想贴太多代码啊，翻起来很烦。P3455[POI2007]ZAP-Queries很基础的一道题。令\(a\leb\)，考虑\(k=1\)的情况。\[\begin{aligned}ans&=\sum\limits_{i=1}^a\sum\limits_{j=......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99