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

数论 莫比乌斯反演

时间：2024-09-13 10:51:40浏览次数：11  
标签：lfloor frac 数论 sum pri rfloor mu 反演 莫比

前置需求

数论分块

概念

对于一个形如 \(\sum_{x=1}^n \lfloor{\frac{n}{x}}\rfloor\) 的式子，我们发现对于一部分的 \(x\)，它们的 \(\lfloor{\frac{n}{x}}\rfloor\) 值相同，因此我们没必要 \(\mathcal{O(n)}\) 计算，可以采用数论分块的办法将这一步的复杂度降低至 \(\mathcal{O(\sqrt{n})}\)。

对于一个已知值 \(n\)，给定一个值 \(l\)，求一个变量 \(r\) 的最大值使得：\(\lfloor{\frac{n}{l}}\rfloor=\lfloor{\frac{n}{r}}\rfloor\)。比较好得出结论，\(r=\lfloor{\frac{n}{\lfloor{\frac{n}{l}}\rfloor}}\rfloor\)。

证明

image

摘自 OI-wiki。

应用

在莫反中通常除 \(n\) 外还有一个 \(m\) 形成双层循环，对于它我们只需更改 \(r\) 的位置使得在 \(i\in \left[l,r\right]\) 中 \(\lfloor{\frac{n}{i}}\rfloor\) 与 \(\lfloor{\frac{m}{i}}\rfloor\) 的值始终不变即可。规定 \(n\le m\)。

if(n>m) swap(n,m);
int res=0;
for(int l=1,r;l<=n;l=r+1)
{
	r=min(n/(n/l),m/(m/l));
	res=/*code*/;
}

线性筛

莫反中必用到的知识点之一。

首先了解莫比乌斯函数：

\[\mu(x)=\begin{cases} 1\qquad\quad n=1\\ 0 \qquad\quad n\,含有平方因子\\ (-1)^k\quad k\,为\, n\,本质不同的质因子个数\end{cases}\]

你需要知道的，一是它是一个积性函数，二是怎么线性筛出它。

从定义能看出，\(\mu\) 函数的值跟质数有关，所以在筛它的同时我们还需要线性筛出质数。

最简单的筛

\(u\) 为 \(\mu\) 函数的值，\(N\) 为值域上界，其他的都是筛素数常见的。

int u[N],pri[N],tot;
bool vis[N];
void Wprepare()
{
	u[1]=1;
	for(int i=2;i<=N;i++)
	{
		if(!vis[i]) pri[++tot]=i,u[i]=-1;
		for(int j=1;j<=tot;j++)
		{
			if(i*pri[j]>N) break;
			vis[i*pri[j]]=1;
			if(i%pri[j]==0) break;
			u[i*pri[j]]=-u[i];
		}
	}
}

莫反通常多测，大多数我们需要在准备工作中多预处理一些式子里的其他函数值，有时候还要对其做求前缀和等一系列操作，这些都是因题而异，需要我们灵活应对。

一定的推式子能力

几个显然的很常用的式子转化：

默认 \(n\le m\)。

基础一点的：

  • \[交换律\sum_x\sum\sum f(x)=\sum_x f(x)\sum\sum \]

  • \[同乘同除，变换上界\sum_{i=1}^n\sum_{j=1}^m [gcd(i,j)=d]=\sum_{i=1}^{\lfloor{\frac{n}{d}}\rfloor}\sum_{j=1}^{\lfloor{\frac{m}{d}}\rfloor}[gcd(i,j)=1] \]

  • \[等价描述，令\,T=dx：\sum_{d=1}^n\sum_{x=1}^{\lfloor{\frac{n}{d}}\rfloor}=\sum_{T=1}^n \sum_{x|T} \]

提高一点的：

  • \[综合上面\sum_{i=1}^n \sum_{j=1}^m f(gcd(i,j))=\sum_{d=1}^n f(d)\sum_{i=1}^{\lfloor{\frac{n}{d}}\rfloor} \sum_{j=1}^{\lfloor{\frac{m}{d}}\rfloor} \;[gcd(i,j)=1] \]

  • \[枚举因数，去循环\sum_{i=1}^n\sum_{j=1}^m\sum_{x|gcd(i,j)} \mu(x)=\sum_{x=1}^n \mu(x)\lfloor{\frac{n}{x}}\rfloor\lfloor{\frac{m}{x}}\rfloor \]

  • 枚举分母，方便数论分块
    令 \(T=dx\)

\[\begin{aligned} Ans &= \sum_{d=1}^n f(d) \sum_{x=1}^{\lfloor{\frac{n}{d}}\rfloor} \mu(x) \lfloor{\frac{n}{dx}}\rfloor \lfloor{\frac{m}{dx}}\rfloor \\ &= \sum_{T=1}^n \lfloor{\frac{n}{T}}\rfloor \lfloor{\frac{m}{T}}\rfloor \sum_{d|T} f(d) \mu(\frac{T}{d}) \end{aligned} \]

主体

由于蒟蒻不会卷积和其他的东西，所以只用到了最基础的一个反演公式

反演公式：

\[[gcd(i,j)=1]=\sum_{d|gcd(i,j)} \mu(d) \]

这是根据莫比乌斯函数的一个性质推出来的：

\[\sum_{d|n}=\begin{cases}1\quad n=1 \\ 0 \quad n\neq 1\end{cases} \]

该性质证明如下：

image

摘自 OI-wiki。

如果你和我一样对这类式子没有什么太强烈的求知欲，那么食用方法如下：

  • 根据题意，推出式子；
  • 尽可能向 \([gcd(i,j)=1]\) 的方向推，然后使用反演公式；
  • 结合上面的式子转化，推出一个可以预处理出函数值，并能运用数论分块优化复杂度的式子，然后 AC 开始调代码。

例题

做莫反的题我认为关键就在刷题，在不断地推式子中寻找共性，熟能生巧。

先推荐一篇学案，上面的推式子技巧都是循序渐进的，比较好。个人推荐一种学习方式：前几道较基础的题可以看着题解的式子一点一点理解，然后回过头来尝试自己独立完成推式子，再到不断优化筛法。

前几题式子部分会写的详细一点，可能导致篇幅冗长请见谅 qwq。

注：以下题未说明均默认 \(n\le m\)。

YY 的 GCD

这道题虽然在第一题的位置，但要考虑的其实还挺多的，综合了上面几乎所有的推式子技巧。

\[\begin{aligned} Ans&= \sum_{i=1}^n\sum_{j=1}^m \;[gcd(i,j)\in prime] \\ &= \sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^m \;[gcd(i,j)=d]\;(d\in prime)\\ &= \sum_{d=1}^n\sum_{i=1}^{\lfloor{\frac{n}{d}}\rfloor}\sum_{j=1}^{\lfloor{\frac{m}{d}}\rfloor} \;[gcd(i,j)=1]\;(d\in prime)\\ &=\sum_{d=1}^n\sum_{i=1}^{\lfloor{\frac{n}{d}}\rfloor}\sum_{j=1}^{\lfloor{\frac{m}{d}}\rfloor}\sum_{x|gcd(i,j)}\mu(x)\;(d\in prime)\\&= \sum_{d=1}^n\sum_{x=1}^{\lfloor{\frac{n}{d}}\rfloor}\;\mu(x) \lfloor{\frac{n}{dx}}\rfloor\lfloor{\frac{m}{dx}}\rfloor \;(d\in prime) \end{aligned} \]

令 \(T=dx\)，则有：

\[\begin{aligned}Ans&= \sum_{T=1}^n\sum_{d|T} \;\mu(\frac{T}{d})\lfloor{\frac{n}{T}}\rfloor\lfloor{\frac{m}{T}}\rfloor (d\in prime)\\&= \sum_{T=1}^n\;\lfloor{\frac{n}{T}}\rfloor\lfloor{\frac{m}{T}}\rfloor \sum_{d|T} \;\mu(\frac{T}{d})(d\in prime) \end{aligned} \]

发现 \(g(T)= \sum_{d|T} \mu(\frac{T}{d})\) 是可以通过枚举质数的倍数提前处理出来的，对它求前缀和，然后数论分块即可。

点击查看代码 
#include<bits/stdc++.h>
using namespace std;
const int Ratio=0;
const int N=1e7+5,M=1e7;
int u[N],pri[N],tot,yz[N],g[N];
void Wpre()
{
    u[1]=1;
    for(int i=2;i<=M;i++)
    {
        if(!yz[i]) pri[++tot]=i,u[i]=-1;
        for(int j=1;j<=tot;j++)
        {
            if(i*pri[j]>M) break;
            yz[i*pri[j]]=1;
            if(i%pri[j]==0) break;
            u[i*pri[j]]=-u[i];
        }
    }
    for(int i=1;i<=tot;i++) for(int j=1;j<=M;j++)
    {
        if(pri[i]*j>M) break;
        g[pri[i]*j]+=u[j];
    }
    for(int i=2;i<=M;i++) g[i]+=g[i-1];
}
int main()
{
    Wpre();
    int T,n,m;scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        if(n>m) swap(n,m);
        long long res=0;
        for(int l=1,r;l<=n;l=r+1)
            r=min(n/(n/l),m/(m/l)),res+=1ll*(g[r]-g[l-1])*(n/l)*(m/l);
        printf("%lld\n",res);
    }
    return Ratio;
}

约数个数和

个人感觉较简单的一道，要点在于求证 \(d(i,j)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]\)

简证

image

摘自洛谷 Siyuan 的题解。

\[\begin{aligned}Ans&= \sum_{i=1}^n\sum_{j=1}^m\;d(ij)\\&= \sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}\;[gcd(x,y)=1]\\&=\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}\sum_{d|gcd(x,y)}\mu(d)\\&=\sum_{i=1}^n\sum_{j=1}^m\;\lfloor{\frac{n}{i}}\rfloor\lfloor{\frac{m}{j}}\rfloor\sum_{d|gcd(i,j)}\mu(d)\\&=\sum_{d=1}^n\sum_{i=1}^{\lfloor{\frac{n}{d}}\rfloor}\sum_{j=1}^{\lfloor{\frac{m}{d}}\rfloor}\lfloor{\frac{n}{id}}\rfloor\lfloor{\frac{m}{jd}}\rfloor\mu(d)\\&=\sum_{d=1}^n\;\mu(d)\sum_{i=1}^{\lfloor{\frac{n}{d}}\rfloor}\sum_{j=1}^{\lfloor{\frac{m}{d}}\rfloor} \lfloor{\frac{n}{id}}\rfloor\lfloor{\frac{m}{jd}}\rfloor\\&=\sum_{d=1}^n\;\mu(d)\,(\sum_{i=1}^{\lfloor{\frac{n}{d}}\rfloor}\,\lfloor{\frac{n}{id}}\rfloor)\,(\sum_{j=1}^{\lfloor{\frac{m}{d}}\rfloor}\,\lfloor{\frac{m}{jd}}\rfloor) \end{aligned} \]

后面两坨看着就很熟悉是不是，没错就是数论分块的模板。这道题范围是 \(n\le 5\times10^5\)，比较小，所以直接对 \(\mu(d)\) 取前缀和，并 \(\mathcal{O(n\sqrt{n})}\) 预处理出后面 \(g(n)=\sum_{i=1}^n \lfloor{\frac{n}{i}}\rfloor\) 值，再运用数论分块即可，查询复杂度 \(\mathcal{O(T\sqrt{n})}\)。

点击查看代码 
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int Ratio=0;
const int N=5e4+5,M=5e4;
int u[N],pri[N],tot,yz[N],sum[N];
ll g[N];
void Wpre()
{
    u[1]=1;
    for(int i=2;i<=M;i++)
    {
        if(!yz[i]) pri[++tot]=i,u[i]=-1;
        for(int j=1;j<=tot;j++)
        {
            if(i*pri[j]>M) break;
            yz[i*pri[j]]=1;
            if(i%pri[j]==0) break;
            u[i*pri[j]]=-u[i];
        }
    }
    for(int i=1;i<=M;i++) sum[i]=sum[i-1]+u[i];
    for(int i=1;i<=M;i++)
    {
        ll res=0;
        for(int l=1,r;l<=i;l=r+1)
            r=i/(i/l),res+=1ll*(r-l+1)*(i/l);
        g[i]=res;
    }
}
int main()
{
    Wpre();
    int T,n,m;scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        if(n>m) swap(n,m);
        ll res=0;
        for(int l=1,r;l<=n;l=r+1)
            r=min(n/(n/l),m/(m/l)),res+=(sum[r]-sum[l-1])*g[n/l]*g[m/l];
        printf("%lld\n",res);
    }
    return Ratio;
}

数表

都说是板子题，但我打了三天。

按照能把题做下去的思路，我们先不考虑 \(a\) 的限制，设 \(\sigma (x)\) 为 \(x\) 的因数和，那么显然有：

\[\begin{aligned}Ans&=\sum_{i=1}^n\sum_{j=1}^m\;\sigma(gcd(i,j))\\&= \sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^m \;[gcd(i,j)=d]\;\sigma(d)\\&=\sum_{d=1}^n\sum_{i=1}^{\lfloor{\frac{n}{d}}\rfloor{}}\sum_{j=1}^{\lfloor{\frac{m}{d}}\rfloor{}}\;[gcd(i,j)=1]\;\sigma(d)\\&=\sum_{d=1}^n\sum_{i=1}^{\lfloor{\frac{n}{d}}\rfloor{}}\sum_{j=1}^{\lfloor{\frac{m}{d}}\rfloor{}}\sum_{x|gcd(i,j)}\mu(x)\,\sigma(d)\\&= \sum_{d=1}^n\;\sigma(d)\sum_{x=1}^{\lfloor{\frac{n}{d}}\rfloor{}}\;\mu(x)\lfloor{\frac{n}{dx}}\rfloor{}\lfloor{\frac{m}{dx}}\rfloor{} \end{aligned} \]

令 \(T=dx\)，则有：

\[\begin{aligned}Ans&= \sum_{T=1}^n \sum_{d|T} \;\sigma(d)\,\mu(\frac{T}{d})\,\lfloor{\frac{n}{T}}\rfloor{}\lfloor{\frac{m}{T}}\rfloor{}\\&=\sum_{T=1}^n\;\lfloor{\frac{n}{T}}\rfloor{}\lfloor{\frac{m}{T}}\rfloor{}\sum_{d|T}\;\sigma(d)\,\mu(\frac{T}{d}) \end{aligned} \]

不会求 \(\sigma\) 函数的看这里。

化到这一步，后面的部分已经可以提前处理了，此时考虑加入 \(a\) 的限制条件。

令 $g(T)=\sum_{d|T} \sigma(d),\mu(\frac{T}{d}) $，当 \(\sigma(d)\le a\) 时会对 \(g(T)\) 产生贡献，而对于所有的多测，改变的只是矩形的规格，并不是数值。。。

那么我们完全可以离线下来做！讲所有询问按 \(a\) 升序排序，每当 \(a\) 的值变大时，对有变动的地方插入相应的值。恰好我们所需的是前缀和且带修，所以考虑用树状数组去维护 \(g(T)\) 函数的前缀和。

插入值的复杂度近似于调和级数，树状数组更新复杂度为 \(\mathcal{O(\log n)}\)，故修改总复杂度为 \(\mathcal{O(n\log^2 n)}\)；采用数论分块优化查询 \(\mathcal{O(\sqrt{n})}\)，树状数组查询 \(\mathcal{O(\log n)}\)，故查询总复杂度为 \(\mathcal{O(q\sqrt{n}\log n)}\)。程序总复杂度 \(\mathcal{O(n\log^2 n+q\sqrt{n}\log n)}\)。

点击查看代码 
#include<bits/stdc++.h>
#define _(a,b) make_pair(a,b)
#define fi first
#define se second
typedef long long ll;
using namespace std;
const int Ratio=0;
const int N=1e5+5,M=1e5;
int u[N],pri[N],tot,yz[N],low[N];
int ans[N],v[N];
pair<int,int> o[N];
struct rmm{int n,m,a,id;}q[N];
bool cmp(rmm A,rmm B){return A.a<B.a;}
void Wpre()
{
    u[1]=1,o[1]=_(1,1);
    for(int i(2);i<=M;i++)
    {
        if(!yz[i]) pri[++tot]=i,u[i]=-1,low[i]=i+1,o[i]=_(i+1,i);
        for(int j(1);j<=tot;j++)
        {
            if(i*pri[j]>M) break;
            yz[i*pri[j]]=1;
            if(i%pri[j]==0)
            {
                low[i*pri[j]]=low[i]*pri[j]+1;
                o[i*pri[j]]=_(o[i].fi/low[i]*low[i*pri[j]],i*pri[j]);
                break;
            }
            u[i*pri[j]]=-u[i];
            low[i*pri[j]]=pri[j]+1;
            o[i*pri[j]]=_(o[i].fi*o[pri[j]].fi,i*pri[j]);
        }
    }
    sort(o+1,o+M+1);
}
void Wupd(int x,int k){for(;x<=M;x+=(x&-x)) v[x]+=k;}
int Wq(int x)
{
    int res=0;
    while(x) res+=v[x],x-=(x&-x);
    return res;
}
int main()
{
    Wpre();
    int T;scanf("%d",&T);
    for(int i(1);i<=T;i++) scanf("%d%d%d",&q[i].n,&q[i].m,&q[i].a),q[i].id=i;
    sort(q+1,q+1+T,cmp);
    int j=1;
    for(int i(1);i<=T;i++)
    {
        while(j<=M&&o[j].fi<=q[i].a)
        {
            for(int k(o[j].se);k<=M;k+=o[j].se)
                Wupd(k,o[j].fi*u[k/o[j].se]);
            j++;
        }
        int res=0,n=q[i].n,m=q[i].m;
        if(n>m) swap(n,m);
        for(int l(1),r;l<=n;l=r+1)
            r=min(n/(n/l),m/(m/l)),res+=(Wq(r)-Wq(l-1))*(n/l)*(m/l);
        ans[q[i].id]=res;
    }
    for(int i(1);i<=T;i++) printf("%d\n",(ans[i]&(~(1<<31))));
    return Ratio;
}

DZY Loves Math

有新函数，先不管它，推式子。

\[\begin{aligned}Ans&=\sum_{i=1}^n\sum_{j=1}^m \;f(gcd(i,j))\\ &=\sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^m\;[gcd(i,j)=d] \,f(d)\\&=\sum_{d=1}^n\sum_{i=1}^{\lfloor{\frac{n}{d}}\rfloor{}}\sum_{j=1}^{\lfloor{\frac{m}{d}}\rfloor{}}\;[gcd(i,j)=1]\,f(d)\\&=\sum_{d=1}^n\;f(d)\sum_{i=1}^{\lfloor{\frac{n}{d}}\rfloor{}}\sum_{j=1}^{\lfloor{\frac{m}{d}}\rfloor{}}\sum_{x|gcd(i,j)}\mu(x)\\&=\sum_{d=1}^n\;f(d)\sum_{x=1}^{\lfloor{\frac{n}{d}}\rfloor{}}\;\mu(x)\lfloor{\frac{n}{dx}}\rfloor{}\lfloor{\frac{m}{dx}}\rfloor{} \end{aligned} \]

令 \(T=dx\)，则有：

\[\begin{aligned}Ans&=\sum_{T=1}^n\;\lfloor{\frac{n}{T}}\rfloor{}\lfloor{\frac{m}{T}}\rfloor{}\sum_{d|T}\;f(d)\,\mu(\frac{T}{d}) \end{aligned} \]

到这一步似乎就可以做了，不过后面的那坨 $g(T)=\sum_{d|T}\ f(d)\ \mu(\frac{T}{d}) $ 需要调和级数预处理，\(n\le 10^7\)，在一个月前的题库上是能跑过的，不过现在不知道为什么速度慢了一半，所以需要我们继续优化，用线性复杂度处理出。

我们着眼于 \(g(T)\) 这个函数。设 \(T\) 共有 \(k\) 个不同的质因子，将其分解为 $T=\prod_{i=1}^k\ p_i^{a_i} $ 。令 \(T\) 的一个因子 \(d\) 分解为 \(d=\prod_{i=1}^k \;p_i^{b_i}\)，发现 \(d\) 有贡献当且仅当 \(\mu(\frac{T}{d})\neq 0\)，即 \(\forall i\in[1,k], \;a_i-b_i\le 1\)，换句话说 \(b_i\) 的取值只能是 \(a_i\) 或 \(a_i-1\)。

然后再分两种情况：

一种是 \(a_i\) 不全相等的情况，此时必有 $存在 \ i,j\in\ [1,k],a_i\lt a_j $，考虑 \(b_i\) 无论取 \(a_i\) 或 \(a_i-1\)，不会对 \(f(T)\) 的值产生影响，且两种取法的 \(\mu\) 值之和为 \(0\)，即：此时无论如何分配 \(b_i\) 的值，最终结果总能两两分配出相加为 \(0\) 的情况，故 \(g(T)=0\)。

另外就是 \(a_i\) 全部相等的情况。此时有贡献的 \(d\) 共有 \(2^k\) 种取值，已知 \(\binom{0}{k}+\binom{2}{k}+\cdots+\binom{2\times \lfloor{\frac{k}{2}}\rfloor{}}{k}=\binom{1}{k}+\binom{3}{k}+\cdots+\binom{2\times \lfloor{\frac{k-1}{2}}\rfloor{}+1}{k}\)，即杨辉三角中每行的奇数项和等于偶数项和。括号中上面的数恰好可对应 \(a_i-b_i\) 中值为 \(1\) 的数量，即在 \(f(d)\) 均相同的情况下，\(g(T)\) 的值是 \(0\)。但当括号中上面的数等于 \(k\)，即 \(\forall \;i\in[1,k],b_i=a_i-1\) 时，\(f(d)=a_i-1\)。

稍微理解下，然后再来分情况。若 \(k\) 为奇数，则当 \(\forall\;i\in[1,k],b_i=a_i-1\) 时，\(\mu(\frac{T}{d})=(-1)^k=-1\)，也就是说，在对结果产生贡献的那一步中本应该减去 \(a_i\)，但实际上减去了 \(a_i-1\)，那么最终 \(g(T)=1\)；若 \(k\) 为偶数同理，此时 \(\mu(\frac{T}{d})=1\)，那么本应该加上 \(a_i\)，但实际上只加了 \(a_i-1\)，最终 \(g(T)=-1\)。

整合一下，发现 \(g\) 函数的取值如下：

\[g(T)=\begin{cases}0\quad\quad\quad\quad 存在 \; i,j\in[1,k],a_i\lt a_j\\ (-1)^{k+1}\quad\, \forall\;i,j\in[1,k],a_i=a_j \end{cases} \]

其中 \(k\) 为 \(T\) 的质因子个数。

实现中，记录最小质因子的指数和它的指数次幂，转移时判断除去最小质因子后次小质因子的指数是否与之相同即可。

预处理 \(g\) 函数及前缀和的复杂度为 \(\mathcal{O(n)}\)，数论分块优化后查询复杂度为 \(\mathcal{O(T\sqrt{n})}\)，总复杂度 \(\mathcal{O(n+T\sqrt{n})}\)。

点击查看代码 
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int Ratio=0;
const int N=1e7+5,M=1e7;
int n,m;
int u[N],pri[N],tot,yz[N],Index[N],low[N],g[N];
void Wpre()
{
    u[1]=1,g[1]=0;
    for(int i(2);i<=M;i++)
    {
        if(!yz[i]) low[i]=pri[++tot]=i,u[i]=-1,Index[i]=g[i]=1;
        for(int j(1);j<=tot;j++)
        {
            if(i*pri[j]>M) break;
            yz[i*pri[j]]=1;
            if(i%pri[j]==0)
            {
                Index[i*pri[j]]=Index[i]+1;
                low[i*pri[j]]=low[i]*pri[j];
                if(low[i]==i) g[i*pri[j]]=1;
                else g[i*pri[j]]=Index[i/low[i]]==Index[i*pri[j]]?-g[i/low[i]]:0;
                break;
            }
            u[i*pri[j]]=-u[i];
            Index[i*pri[j]]=1;
            low[i*pri[j]]=pri[j];
            g[i*pri[j]]=Index[i]==1?-g[i]:0;
        }
    }
    for(int i(2);i<=M;i++) g[i]+=g[i-1];
}
int main()
{
    Wpre();
    int T;scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        if(n>m) swap(n,m);
        ll res=0;
        for(int l(1),r;l<=n;l=r+1)
            r=min(n/(n/l),m/(m/l)),res+=1ll*(g[r]-g[l-1])*(n/l)*(m/l);
        printf("%lld\n",res);
    }
    return Ratio;
}

其他例题会逐渐更新。

制作不易，如有帮助，请推荐支持，感谢！

标签：lfloor,frac,数论,sum,pri,rfloor,mu,反演,莫比
From： https://www.cnblogs.com/Ratio-Yinyue1007/p/18406172

相关文章

  • 二项式反演学习笔记
    前言万字长文！这里有我的一些思考和领会，网络上的教程都太潦草了。并且我发现了新的反演公式！概述二项式反演用于转化两个具有特殊关系的函数\(f\)和\(g\)，从而方便求解问题。一般来说，直接计算恰好满足\(n\)个限制的答案不好求，但是可以计算出“至少”/“至多”满足\(n\)......
  • 数论
    1.欧拉函数我们定义\(\varphi(n)=\sum^n_{i=1}[\gcd(i,n)==1]\)。特殊的当\(n\)为质数的时候，\(\varphi(n)=n-1\)。假如我们定义\(n=p_1^{a_1}\timesp_2^{a_2}\times\cdots\cdots\timesp_k^{a_k}\)，那么\(\varphi(n)=n\times\dfrac{p_1-1}{p_1}\t......
  • Luogu P11036 GCD 与 LCM 问题 [ 蓝 ] [ 构造 ] [ 数论 ] [ adhoc ]
    LuoguP11036GCD与LCM问题：梦熊的题真是又神又逆天。思路观察到有个奇数的特殊性质，我们尝试从奇数构造入手。先来尝试带入极端数据，对于\(\gcd\)，我们可以把\(b=1\)的情况先带进去看看。\[a+b+c+d=\gcd(a,b)+\operatorname{lcm}(c,d)\]\[a+1+c+d=1+\operatorname{lcm}(c,......
  • 莫比乌斯反演入门
    来自这位大佬的视频的整理先整理几个重要的数论函数。1.莫比乌斯函数$\mu(n)$当\(n=1\)时取1，当\(n\)存在平方因子的时候取0，否则取\((-1)^k\)，其中\(k\)是\(n\)所含的质因子数量。2.欧拉函数\(\phi(n)=\displaystyle\sum_{d=1}^n[gcd(d,n)=1]\)，就是小于等于n且与\(n\)互质......
  • 学习笔记：数论分块
    数论分块1.0可以快速计算一些含有除法向下取整的和式（形如$\sum_{i=1}^ng(i)\left\lfloor\frac{n}{i}\right\rfloor$）。2.0引理1：\(\left\lfloor\frac{n}{i}\right\rfloor\)的取值最多只有\(2\times\sqrtn\)种。证明：对于\(i\le\left\lfloor\sqrtn\rig......
  • 数论四大定理——裴蜀定理
    好久不见，开学和假期天天搞csp实在没时间搞CSDN,终于抽出一点时间来写会文章了。我们先来看一道NOIP提高组的题目题目描述小凯手中有两种面值的金币，两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下，仅凭这两种金币，有些物品他是无法准确支付的。现在......
  • 数论分块扩展
    【OI-wiki#5805】feat(math/number-theory/sqrt-decomposition.md):增加数论分块的拓展&改动部分格式以计算含有\(\left\lfloor\sqrt{\frac{n}{d}}\right\rfloor\)的和式为例。考虑对于一个正整数\(n\)，如何求出集合\[S=\left\{\left\lfloor\sqrt{\frac{n}{d}}\right\rf......
  • 数论基础
    数论基础数论函数数论函数是指这样一类函数：其定义域是正整数，值域是一个数集。定义两个数论函数的加法，为逐项相加，即\((f+g)(n)=f(n)+g(n)\)。定义数乘这个数和每一项都相乘，即\((xf)(n)=x\timesf(n)\)。常见数论函数\[1(x)=1\\\epsilon(x)=[x=1]\\id(......
  • 数论 Part : Dirichlet 卷积 & 莫比乌斯反演 & 杜教筛
    \(\text{-1前言}\)\(\text{-1.0日志}\)24.08.24：启动本文企划，正式着笔。\(\text{-1.1本文记号说明}\)本文使用\(\cdot\)表示乘号，\(*\)表示卷积，\(\mathbb{P}\)表示质数集。\(\text{0基础函数科技}\)单位函数\({\bf1}(x)=1\)。幂函数\(id^k(x)=x^k\)。恒等函数（幂......
  • 部分数论函数结论的证明
    从莫比乌斯反演的文章里迁移出来的。部分数论函数结论的证明前面的小节中，我们使用了一些数论函数相关的结论，但并未给出证明。接下来我们来证明它们。欧拉函数证明\[\varphi(ij)=\dfrac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))}\]由欧拉函数公式，设\(x......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99