函数定义
\[\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} \]- 证明: