精华内容
下载资源
问答
  • 莫比乌斯反演题目

    2019-05-03 21:01:47
    莫比乌斯反演定理两种形式的证明 目录 1.luogoP2568GCD 2.luoguP2257 YY的GCD 1.luogoP2568 GCD 题目链接 莫比乌斯反演的入门题。 思路: 设 代码: #include<iostream> #...

    持续更新ing

    唔。从年前就想要搞,但是一直鸽到现在。

    不过,就从现在开始吧!!!

    前导知识

    莫比乌斯反演定理两种形式的证明

    目录

    1.luogoP2568 GCD

    2.luoguP2257 YY的GCD

     

    1.luogoP2568 GCD 

    题目链接

    莫比乌斯反演的入门题。

    思路:

    ans=\sum _{i=1}^{n}\sum _{j=1}^{n}[gcd(i,j)=prim]=\sum _{d=1}^{n}[d=prim] \sum _{i=1}^{\frac{n}{d}}\sum _{j=1}^{\frac{n}{d}}[gcd(i,j)=1]

    g\left ( n \right )=\sum _{i=1}^{n}\sum _{j=1}^{n}[gcd(i,j)=1]= \sum _{i=1}^{n}\sum _{j=1}^{n}\sum _{d|gcd(i,j)}u\left ( d \right )= \sum _{d=1}^{n}\left ( \frac{n}{d} \right )^2u(d)

    ans=\sum _{d=1}^{n}[d=prim]g\left ( \frac{n}{d} \right )

    代码:

    #include<iostream>
    #include<cstdio>
    #include<cmath>
    using namespace std;
    const int N=1e7+100;
    int n;
    long long ans;
    int vis[N],u[N],sum[N];
    int p[N];
    int cnt=0;
    void seive(){
    	vis[0]=1;
    	vis[1]=1;
    	u[1]=1;
    	for(int i=2;i<=n;++i){
    		if(!vis[i])p[cnt++]=i,u[i]=-1;
    		for(int j=0;j<cnt&&(long long)p[j]*i<=n;++j){
    			vis[p[j]*i]=1;
    			u[p[j]*i]=-u[i];
    			if(i%p[j]==0){
    				u[p[j]*i]=0;
    				break;
    			}
    		}
    	}
    	for(int i=1;i<=n;++i)sum[i]=sum[i-1]+u[i];
    }
    long long g(int n){
    	long long ans=0;
    	for(int l=1,r;l<=n;l=r+1){
    		r=n/(n/l);
    		ans+=(long long)(n/l)*(n/l)*(sum[r]-sum[l-1]);
    	}
    	return ans;
    }
    int main(){
    	scanf("%d",&n);
    	seive();
    	ans=0;
    	for(int i=0;i<cnt;++i)
    		ans+=g(n/p[i]);
    	printf("%lld\n",ans);
    	return 0;
    } 
    

    2.luoguP2257 YY的GCD

    题目链接

    思路:

    设    f\left ( n \right )=\sum _{n|d}[gcd\left ( i,j \right )=n]  ,F\left ( n \right )=\sum _{n|d}f\left ( d \right )=\frac{N}{n}*\frac{M}{n}

    ans=\sum _{i=1}^{N}\sum _{j=1}^{M}[gcd(i,j)\in \mathbb{P}]=\sum _{n=1,n\in \mathbb{P}}^{min\left ( N,M \right )} \sum _{i=1}^{N}\sum _{j=1}^{M}[gcd(i,j)=n]=\sum _{n=1,n\in \mathbb{P}}^{min\left ( N,M \right )}f\left ( n \right )

    根据莫比乌斯反演定理F\left ( n \right )=\sum _{n|d}f\left ( d \right )     =>     f\left ( n \right )=\sum _{n|d}u\left ( \frac{d}{n} \right )F\left ( d \right ) 得,

    ans=\sum _{n=1,n\in \mathbb{P}}^{min\left ( N,M \right )}\sum _{n|d}u\left ( \frac{d}{n} \right )F\left ( d \right )=\sum _{n=1,n\in \mathbb{P}}^{min\left ( N,M \right )}\sum _{n|d}u\left ( \frac{d}{n} \right )\frac{N}{d}\frac{M}{d}

    =\sum_{d=1}^{N}\frac{N}{d}\frac{M}{d}\sum _{n|d,n\in \mathbb{P}}u\left ( \frac{d}{n} \right )

    g\left ( d \right )=\sum _{n|d,n\in \mathbb{P}}u\left ( \frac{d}{n} \right )

    筛的时候先O\left ( n \right )筛出来u\left ( n \right ),再求g\left ( n \right ),求g\left ( n \right )得时候时间复杂度跟埃氏筛差不多。再对g\left ( n \right )求前缀和。

    然后就是整除分块的套路写法了。

    代码:

    #include<iostream>
    #include<cstdio>
    using namespace std;
    const int N=1e7+100;
    int vis[N],u[N],p[N];
    long long g[N],sum[N],ans;
    int cnt,t,n,m;
    void seive(){
    	vis[1]=1;
    	u[1]=1;
    	for(int i=2;i<N;++i){
    		if(!vis[i]){
    			p[cnt++]=i;
    			u[i]=-1;
    		}
    		for(int j=0;j<cnt&&(long long)p[j]*i<N;++j){
    			vis[p[j]*i]=1;
    			u[p[j]*i]=-u[i];
    			if(i%p[j]==0){
    				u[p[j]*i]=0;
    				break;
    			}
    		}
    	}
    	for(int i=0;i<cnt;++i)
    		for(int j=1;(long long)p[i]*j<N;++j)
    			g[p[i]*j]+=u[j];
    	for(int i=1;i<N;++i)sum[i]=sum[i-1]+g[i];
    }
    long long cal(int n,int m){
    	long long ans=0;
    	for(int l=1,r;l<=n;l=r+1){
    		r=min(n/(n/l),m/(m/l));
    		ans+=(long long)(n/l)*(m/l)*(sum[r]-sum[l-1]);
    	}
    	return ans;
    }
    int main(){
    	seive();
    	scanf("%d",&t);
    	while(t--){
    		scanf("%d%d",&n,&m);
    		if(n>m)n^=m^=n^=m;
    		ans=cal(n,m);
    		printf("%lld\n",ans);
    	}
    	return 0;
    } 

     

    展开全文
  • 不定期更新: (只更新写了题解的题) 1:CodeForces - 645F Cowslip Collections ...我参考的做题列表:莫比乌斯反演题目列表及题解 一些对反演有用的博客: 1:POPOQQQ的课件,百度一大堆 2:高...

    不定期更新:
    (只更新写了题解的题)
    1:CodeForces - 645F Cowslip Collections
    分数:2500
    题解:锟斤拷烫烫烫

    2:UVA 11426 - GCD - Extreme (II)
    题解:锟斤拷烫烫烫

    3:51nod 1192
    题解:锟斤拷烫烫烫

    我参考的做题列表:莫比乌斯反演题目列表及题解
    一些对反演有用的博客:
    1:POPOQQQ的课件,百度一大堆
    2:高中同学神犇DQS
    3:做题时碰到了新的积性函数怎么筛?筛构造的积性函数,筛通用积性函数

    展开全文
  • 前言: 本题表中,凡是涉及\(n、m\),都默认\(n \leq m\)。 如果你连莫比乌斯求\(\sum_{i=1}^n \sum_{j=1}^m [gcd(i,j)=1]\)都还不会,请去这里先入个门。...这些题目都非常水,莫比乌斯反演入门题, 主要是对莫...

    前言:

    本题表中,凡是涉及\(n、m\),都默认\(n \leq m\)
    如果你连莫比乌斯求\(\sum_{i=1}^n \sum_{j=1}^m [gcd(i,j)=1]\)都还不会,请去这里先入个门。
    题目里面的各种套路还是很深的。
    如果扎扎实实看完(并做完),一般的莫比乌斯反演肯定没问题了(当然不排除一些毒瘤题啦)。

    Part1

    这些题目都非常水,莫比乌斯反演入门题,
    主要是对莫比乌斯反演应用有一个基本概念。

    1.[HAOI2011]Problem b

    (具体题目戳我)
    题目:一组数据(\(a、d、c、d \leq 5×10^4\))求
    \[\sum_{i=a}^{b} \sum_{j=c}^d [gcd(i,j)=d]\]
    题解:
    \[\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] = \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \mu(i)\lfloor \frac{\lfloor \frac{n}{d} \rfloor}{i} \rfloor * \lfloor \frac{\lfloor \frac{m}{d} \rfloor}{i} \rfloor\]
    数论分块,然后二维容斥即可。

    2.[NOI2010]能量采集

    (具体题目戳我)
    题目:一组数据(\(n、m \leq 10^5\)),求
    \[2*\sum_{i=1}^n \sum_{j=1}^m gcd(i,j) - n*m\]
    题解:
    \[\sum_{i=1}^n \sum_{j=1}^m gcd(i,j) =\sum_{d=1}^nd \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} [gcd(i,j)=1] \]
    枚举\(d\),然后用第1题的方法搞即可。

    3.Gcd

    (具体题目戳我)
    题目:一组数据,给定整数\(N(N\leq10^7)\),求\(1 \leq x,y \leq N\)\(Gcd(x,y)\)为素数的组数
    题解:
    \[\sum_{i=1}^n \sum_{j=1}^m gcd(i,j) =\sum_{d=2}^{d \leq n} d\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} [gcd(i,j)=1] \]
    枚举素数\(d\),然后用第1题的方法搞即可。

    4.[中山市选2011]完全平方数

    (具体题目戳我)
    题目:\(50\)组数据,给出\(k\),求第\(k\)个不是完全平方数的倍数的数是多少。\(k \leq 10^9\)
    题解:
    先二分一个\(n\),然后检查\(n\)下面有多少个非完全平方数。计算方法为:
    \(f(i)\)表示只为\(i^2\)倍数,并且不是其它平方数倍数的数的个数。
    那么令\(F(i) = f(i)+f(2i)+....+f(ki)\),即为\((ri)^2\)倍数的数的个数。
    那么\(F(i) = \sum_{i|d} f(d)\)。显然\(F(n) = \lfloor \frac{n}{i^2} \rfloor\)
    反演一下:
    \[f(1) = \sum_{i=1}^{\lceil \sqrt{n} \rceil } \lfloor \frac{n}{i^2} \rfloor\]
    直接数论分块即可得到一个数\(n\)的排名\(f(1)\)

    Part2

    这一部分的题就相当有难度了(跨度这么大我也很无奈啊
    从这些题中,我们可以感受到莫比乌斯反演的一些套路,包括提取公因数、分离变量等。

    5.[BZOJ2154]Crash的数字表格

    (具体题目戳我)
    题目:一组数据,输入\(n\)\(m\),(\(n、m \leq 10^7\)),求:
    \[\sum_{i=1}^n \sum_{j=1}^m lcm(i,j) \quad mod \quad 20101009\]
    题解:
    \[Ans = \sum_{i=1}^n \sum_{j=1}^m lcm(i,j) = \sum_{i=1}^n \sum_{j=1}^m \frac{ij}{gcd(i,j)} = \sum_{d=1}^n \frac{f(n,m,d)}{d}\]
    其中
    \[f(n,m,d) = \sum_{i=1}^n \sum_{j=1}^m [gcd(i,j)=d]*ij = \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{i=1}^{\lfloor \frac{m}{d} \rfloor} ij*[gcd(i,j)=1]*d^2\]
    带回原式中:
    \[Ans = \sum_{d=1}^n d*f({\lfloor \frac{n}{d} \rfloor},{\lfloor \frac{m}{d} \rfloor},1) \]
    考虑一下函数 \(f\) 的求法:
    \[f({n},{m},d) = \sum_{i=1}^{n } \sum_{i=1}^{m } ij*[gcd(i,j)=d] = f(d)\]

    \[F(d) = \sum_{i=1}^{{n}} \sum_{i=1}^{{m}} ij*[d|gcd(i,j)] = \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{i=1}^{\lfloor \frac{m}{d} \rfloor} ij= \sum_{n|d} f(d)\]
    反演一下:
    \[f(i) = \sum_{i|d}\mu(\frac{d}{i})F(d) , f(1) = \sum_{d=1}^n\mu(d)F(d) = \sum_{d=1}^n\mu(d) \sum_{i=1}^{{\lfloor \frac{n}{d} \rfloor}} \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} ij\]
    显然\(\sum_{i=1}^{{n}} \sum_{j=1}^{{m}} ij = \sum_{i=1}^{{n}} i *\sum_{j=1}^{{m}} j = \frac{n*(n+1)}{2} * \frac{m*(m+1)}{2}\)
    总结一下,得到了两个式子:
    \[Ans = \sum_{d=1}^n d*f({\lfloor \frac{n}{d} \rfloor},{\lfloor \frac{m}{d} \rfloor},1) \]
    \[f({n},{m},1) = \sum_{d=1}^n\mu(d) \frac{\lfloor \frac{n}{d} \rfloor*(\lfloor \frac{n}{d} \rfloor+1)}{2} * \frac{\lfloor \frac{m}{d} \rfloor*(\lfloor \frac{m}{d} \rfloor+1)}{2}\]
    两个式子都可以数论分块,所以复杂度为:\(O(\sqrt{n})*O(\sqrt{n})=O({n})\)

    6.[SDOI2015]约数个数和

    (具体题目戳我)
    题目:\(5×10^4\)组数据,输入\(n,m\)\((n,m \leq 5×10^4)\),\(d(x)\)表示\(x\)的约数个数,求:
    \[\sum_{i=1}^n \sum_{j=1}^m d(ij)\]
    题解:
    首先,有定理:
    \[d(ij) = \sum_{t1|i} \sum_{t2|j} [gcd(t1,t2)=1]\]
    证明:
    对于一个约数\(d\),它必定由\(i\)的一个约数与\(j\)的一个约数的乘积。
    为了防止算重,我们规定\(gcd(t1,t2)=1\)才计算。
    因为每一个数一定可以被表示为两个互质的数的乘积,所以这样计算是正确的。
    同样这样的\(t1\)\(t2\)一定存在于\(i\)\(j\)的约数中,因为唯一分解定理
    所以把原式化为:
    \[Ans =\sum_{i=1}^n \sum_{j=1}^m \sum_{t1|i} \sum_{t2|j} [gcd(t1,t2)=1]\]
    四个\(\sum\)很不好看(也不好搞),单独考虑二元组(i,j)的贡献:
    \[Ans = \sum_{u=1}^n \sum_{v=1}^m [gcd(u,v)=1] \lfloor \frac{n}{u} \rfloor \lfloor \frac{m}{v} \rfloor\]

    \[f(d) = \sum_{u=1}^n \sum_{v=1}^m [gcd(u,v)=d] \lfloor \frac{n}{u} \rfloor \lfloor \frac{m}{v} \rfloor\]
    同理令
    \[F(d) = \sum_{u=1}^n \sum_{v=1}^m [d|gcd(u,v)] \lfloor \frac{n}{u} \rfloor \lfloor \frac{m}{v} \rfloor = \sum_{u=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{u=1}^{\lfloor \frac{m}{d} \rfloor} \lfloor \frac{n}{ud} \rfloor \lfloor \frac{m}{vd} \rfloor\]
    所以
    \[F(d) = \sum_{u=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{u=1}^{\lfloor \frac{m}{d} \rfloor} \lfloor \frac{n}{ud} \rfloor \lfloor \frac{m}{vd} \rfloor = \sum_{u=1}^{\lfloor \frac{n}{d} \rfloor} \lfloor \frac{n}{ud} \rfloor *\sum_{u=1}^{\lfloor \frac{m}{d} \rfloor} \lfloor \frac{m}{vd} \rfloor = sum(\lfloor \frac{n}{d} \rfloor)*sum(\lfloor \frac{m}{d} \rfloor)\]
    其中\(sum(x)=\sum_{i=1}^{x} \lfloor \frac{x}{i} \rfloor\)表示\(1\)\(x\)的约数个数和,不懂为什么见这题
    又因为
    \[F(i) = \sum_{i|d}f(d)\]
    莫比乌斯反演一波:
    \[f(1) = \sum_{i=1}^n \mu(i)F(i) = \sum_{i=1}^n \mu(i) sum(\lfloor \frac{n}{i} \rfloor)*sum(\lfloor \frac{m}{i} \rfloor) = Ans\]
    其中\[sum(x)=\sum_{i=1}^{x} \lfloor \frac{x}{i} \rfloor\]
    显然先 数论分块 预处理\(sum(x)\),然后每次询问也数论分块求解\(f(1)\)即可。
    总的复杂度为:预处理\(O(n \sqrt{n})\) , 询问 \(O(T \sqrt{n})\)

    7. [SDOI2017]数字表格

    (具体题目戳我)
    题目:
    \(f(i)\)为斐波那契数列第\(i\)项,定义\(f(0)=0,f(1)=1\)
    总共输入\(10^3\)组数据,每次输入\(n,m\)\((n,m \leq 10^6)\),时限\(5 sec\),求:
    \[\prod_{i=1}^n \prod_{j=1}^m f(gcd(i,j))\]
    题解:
    肯定先要提出\(gcd(i,j)\)
    \[Ans = \prod_{i=1}^n \prod_{j=1}^m f(gcd(i,j)) = \prod_{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}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} [gcd(i,j)=1] = \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \mu(i) {\lfloor \frac{n}{id} \rfloor} {\lfloor \frac{m}{id} \rfloor} = r(\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor)\]
    \[Ans = \prod_{d=1}^n f(d)^{r(\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor)}\]
    显然\(Ans\)\(r(n,m)\)的求解都可以数论分块,此时复杂度为\(O(n)\)可以跑过单组数据。
    但是我们有多组数据,考虑如何优化。
    看到\(id\),是不是感觉很套路?令\(T = id\) , 那么我们把\(T\)给提出来:
    \[\prod_{d=1}^n f(d)^{\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \mu(i) {\lfloor \frac{n}{T} \rfloor} {\lfloor \frac{m}{T} \rfloor}} = \prod_{T=1}^n(\prod_{d|T} f(d)^{\mu(\frac{T}{d})})^{{\lfloor \frac{n}{T} \rfloor} {\lfloor \frac{m}{T} \rfloor}}\]

    \[R(T) = \prod_{d|T} f(d)^{\mu(\frac{T}{d})}\]
    这显然是可以\(O(n log^2(n))\)直接暴力算出来的(因为是枚举因数啊)。
    那么
    \[Ans = \prod_{T=1}^n(\prod_{d|T} f(d)^{\mu(\frac{T}{d})})^{{\lfloor \frac{n}{T} \rfloor} {\lfloor \frac{m}{T} \rfloor}} = \prod_{T=1}^nR(T)^{{\lfloor \frac{n}{T} \rfloor} {\lfloor \frac{m}{T} \rfloor}}\]
    显然\(R(T)\)是可以记乘法前缀和的,所以每次询问时数论分块搞一波即可。
    总的复杂度: 预处理\(O(n log^2(n))\) , 询问\(O(T \sqrt{n}log(n))\)

    Part3

    其实比较关键的题目就是\(Part2\)里的三题了,剩下的这些题当做补充练习。

    8. GCD-2(YY的GCD)

    (具体题目戳我)
    题目:\(10^5\)组数据,给定整数\(N,M(\leq10^7)\),求\(1 \leq x\leq N\) , \(1 \leq y\leq M\) ,且\(Gcd(x,y)\)为素数的组数。
    题解:
    其实就是第三题《\(GCD\)》的升级版。
    前面的步骤直接跳过:
    \[Ans = \sum_{d=1}^n \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \mu(i) \lfloor \frac{n}{id} \rfloor \lfloor \frac{m}{id} \rfloor\]
    老套路,令\(T = id\),提出\(T\)
    \[\sum_{d=1}^n \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \mu(i) \lfloor \frac{n}{id} \rfloor \lfloor \frac{m}{id} \rfloor = \sum_{T=1}^n \sum_{d|T} \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} \mu(\frac{T}{d})\]
    然后只要考虑这个玩意怎么搞即可:
    \[R(T) = \sum_{d|T} \mu(\frac{T}{d})\]
    额...还记得在基础数论讲素数时说的那个结论吗?
    结论回顾: 质数的密度大约是\(\frac{1}{10}\)!
    所以\(O(10^7k) ------> O(10^6k)?\)
    嗯,好像是这样,所以暴力埃式筛即可。

    9. [UVa11426]最大公约数之和——极限版II

    (具体题目戳我)
    题目:\(10^2\)组数据,给定整数\(n,m(\leq10^7)\),求:
    \[\sum_{i=1}^{n-1} \sum_{j=i+1}^n gcd(i,j)\]
    题解:
    其实就是第二题《能量采集》的升级版。
    考虑二元组\((i,j)\)的构成形式,一共三种:\(i<j\)\(i=j\)\(i>j\)
    所以只要求\(\sum_{i=1}^n \sum_{j=1}^n gcd(i,j) = Ans'\),那么显然:
    \[Ans = \frac{(Ans' - \sum_{i=1}^n i)}{2}\]
    下面求\(Ans'\),前面的步骤直接跳过:
    \[Ans' = \sum_{d=1}^n d\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \mu(i) {\lfloor \frac{n}{id} \rfloor }^2\]
    还是老套路(套路就是这么神奇),令\(T = id\),提出\(T\)
    \[Ans' = \sum_{T=1}^n \sum_{d|T} \mu(\frac{T}{d}) {\lfloor \frac{n}{T} \rfloor }^2 d = \sum_{T=1}^n {\lfloor \frac{n}{T} \rfloor }^2\sum_{d|T} \mu(\frac{T}{d}) d \]
    那么显然下面这个东东:
    \[R(x) = \sum_{d|T} \mu(\frac{T}{d})*d\]
    是一个狄利克雷卷积 , 直接积性函数线性筛即可。

    10.HDU4746: \(Mophues\)

    (具体题目戳我)
    名字莫名诡异....
    题目:\(5*10^3\)组数据 , 每次给定一个\(n,m,p\)(\(<=5*10^5\)),求:
    \[\sum_{i=1}^n \sum_{j=1}^m [h(gcd(i,j)) \leq p]\]
    其中其中\(h(x)\)表示一个数质因数分解后质数的个数。例如:\(12=2×2*3\),那么\(h(12)=3\)
    题解:
    非常有意思的一题。
    首先大力化式子(与前面所有题目方法类似):
    \[Ans = \sum_{T=1}^n \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor \sum_{d|T} [h(d) \leq p] \mu(\frac{T}{d}) = \sum_{T=1}^n \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor R(p,T)\]
    考虑如何求\(R(p,T)\)
    \[R(p,T) = \sum_{d|T} [h(d) \leq p] \mu(\frac{T}{d})\]
    发现在\([1,n]\)中,\(h(i) \leq 18\) , (\(2^{18} = 262144\) , \(2^{19} = 524288\)
    所以就非常神奇了 , 当\(18 < p\)时,直接输出\(n*m\)即可。
    所以只要处理\(0 \leq p \leq 18\)的前缀和即可。
    这个还是比较简单的吧,分\(3.5\)步走:
    (0)显然\(h(i)\)在求\(\mu(i)\)时可以顺便求出来。
    (1)埃氏筛处理\(E(p,x) = \sum_{d|T} [h(d) = p] \mu(\frac{T}{d})\)
    (2)统计一下\(S(p,x) = \sum_{i=1}^p E(i,x)\)
    (3)统计一下\(R(p,x) = \sum_{i=1}^x S(p,i)\)
    然后每次询问时直接调用\(R(p,x)\),接着数论分块即可。

    11.[ZOJ3435]Ideal Puzzle Bobble

    (具体题目戳我)
    题目:求:
    \[\sum_{i=1}^L \sum_{j=1}^W \sum_{k=1}^H[gcd(i,j,k)==1]\]
    题解:
    这题应该放到\(Part1\)里去的...
    \[Ans = \sum_{i=1}^{min(L,W,H)} \mu(i) \lfloor \frac{L}{i} \rfloor \lfloor \frac{W}{i} \rfloor \lfloor \frac{H}{i} \rfloor\]

    12.来历不明的火题:

    题目:一组数据,给定\(n,k\)(\(n \leq 10^7\) , \(k \leq 10^5\)) , 求:
    \[\sum_{i=1}^n \sum_{j=1}^m i^kj^k*gcd(i,j)\]
    题解:
    首先先打一个预防针:\(q(i)=i^k\)请线性筛好不然肯定会超时。
    然后先化式子:
    \[Ans = \sum_{d=1}^n d^{2k+1} \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{n}{d} \rfloor}[gcd(i,j)=1]i^kj^k = \sum_{d=1}^n d^{2k+1} R(\lfloor \frac{n}{d} \rfloor)\]
    然后求解\(R(x)\)
    \[f(d) = \sum_{j=1}^{\lfloor \frac{n}{d} \rfloor}[gcd(i,j)=d]i^kj^k \]
    所以构造倍数形式莫比乌斯:
    \[F(d) = \sum_{j=1}^{n}[d|gcd(i,j)]i^kj^k = \sum_{d=1}^{n}d^{2k}\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor \frac{n}{d}\rfloor}i^kj^k\]
    上面这步是关键(提出\(d\)),然后继续化:
    \[F(d) = \sum_{d=1}^{n}d^{2k}\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}i^k *\sum_{j=1}^{\lfloor \frac{n}{d}\rfloor}j^k = \sum_{d=1}^n d^{2k} *[sum(\frac{n}{d})]^2 \ ;\]
    其中\(sum(d)\)为乘法前缀和,预处理一下即可。
    接着就可以莫比乌斯反演了:
    \[R(n) = f(1) = \sum_{d=1}^n \mu(d) F(d) = \sum_{d=1}^n \mu(d) d^{2k} sum(\lfloor \frac{n}{d} \rfloor) \ ;\]
    \[Ans = \sum_{d=1}^n d^{2k+1} R(\lfloor \frac{n}{d} \rfloor)\]
    注意一下$x^{2k}=(x^k)^2  ;  x^{2k+1} = x^{2k}*x $ , 不能用快速幂。
    显然两边都可以数论分块,\(O(n)\)计算即可 , 注意常数问题。

    Part INF

    这里总结一下套路:
    (1)遇见\(id\)形式,换元提出\(T=id\)
    \[Sample=\sum_{d=1}^n \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\mu({i}) \lfloor \frac{n}{id} \rfloor = \sum_{T=1}^n \lfloor \frac{n}{T} \rfloor \sum_{d|T}\mu(\frac{T}{d}) \]
    那么后面那一坨就很有可能可以线性筛、分块(或者搞事情)之类的。
    (2)构造\(F(d)\)时提出公因子\(d\)
    \[Sample = F(d) = \sum_{j=1}^{n}[d|gcd(i,j)]ij = \sum_{d=1}^{n}d\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor \frac{n}{d}\rfloor}ij= \sum_{d=1}^{n}d(\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}i)^2\]
    然后后面的一坨一般就比较好算了,从而达到化简式子的目的。

    转载于:https://www.cnblogs.com/GuessYCB/p/8277359.html

    展开全文
  • 先不考虑质数的影响,直接反演一波设f(x)=∑i=1N∑j=1M[gcd(i,j)=x]设g(x)为公约数为x及x的倍数的数量g(x)=∑i=1N∑j=1M[x∣gcd(i,j)]=⌊Nx⌋⌊Mx⌋f(x)=∑x∣dμ(dx)g(d)=∑x∣dμ(dx)⌊Nd⌋⌊Md⌋显然f(x)可以数论...

    YYGCDYY的GCD

    N,M,1xN,1yMgcd(x,y)(x,y)给定 N, M,求 1≤x≤N,1≤y≤M 且 \gcd(x,y) 为质数的 (x, y) 有多少对。

    ---------------------------------
    令N <= M
    p=2Ni=1Nj=1M[gcd(i,j)=p],f(x)=i=1Nj=1M[gcd(i,j)=x]g(x)xxg(x)=i=1Nj=1M[xgcd(i,j)]=NxMxf(x)=xdμ(dx)g(d)=xdμ(dx)NdMdf(x)μnμ0 \displaystyle\sum^N_{p=2}\displaystyle\sum^{N}_{i = 1}{\displaystyle\sum^M_{j=1}} [\gcd(i,j)=p] \\先不考虑质数的影响,直接反演一波 \\设f(x) = \sum^N_{i=1}\sum^M_{j=1}[gcd(i,j)=x] \\设g(x)为公约数为x及x的倍数的数量 \\g(x) = \sum^N_{i=1}\sum^M_{j=1}[x|gcd(i,j)] = \lfloor {\frac{N}{x}} \rfloor \lfloor {\frac{M}{x}} \rfloor \\f(x) = \sum_{x|d} \mu(\frac{d}{x})g(d) = \sum_{x|d}\mu(\frac{d}{x})\lfloor {\frac{N}{d}} \rfloor \lfloor {\frac{M}{d}} \rfloor \\显然f(x)可以数论分块求 \\接下来要考虑质数,实际上只需要在筛\mu 的时侯只做素数的前n项和就可以,即非素数时\mu始终为0
    ---------------------------------
    约数个数和

    d(x)xn,m设 d(x) 为 x 的约数个数,给定 n,m,求
    i=1nj=1md(ij)\sum^n_{i=1}\sum^m_{j=1}d(i*j)
    引理:d(xy)=ixjy[gcd(i,j)=1]d(x*y) = \sum_{i|x} \sum_{j|y} [\gcd(i,j) =1]

    证明

    x=1ny=1mixjy[gcd(i,j)=1]iji=1nj=1mnimj[gcd(i,j)=1]1[gcd(i,j)=1]=dgcd(i,j)μ(d)i=1nj=1mnimjdgcd(i,j)μ(d)dgcd(i,j)d=1nμ(d)i=1nj=1m[(di)and(dj)]nimjd=1nμ(d)i=1ndj=1mdnidmjdi=1nni, \\原式化为:\sum^n_{x=1}\sum^m_{y=1}\sum_{i|x} \sum_{j|y} [\gcd(i,j) =1] \\转换枚举项,枚举i和j \\\sum^n_{i=1}\sum^m_{j=1} \lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{j} \rfloor [\gcd(i,j)=1] \\套路1:[gcd(i,j)=1] = \sum_{d|gcd(i,j)} \mu(d) \\\sum^n_{i=1}\sum^m_{j=1} \lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{j} \rfloor \sum_{d|gcd(i,j)} \mu(d) \\接下来枚举d,此时可以通过变换把gcd(i,j)去掉 \\\sum^n_{d = 1}\mu(d) \sum_{i = 1}^n\sum_{j = 1}^m[(d|i) and(d|j)]\lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{j} \rfloor \\\sum^n_{d = 1}\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_{i=1}^n\lfloor \frac{n}{i} \rfloor ,再数论分块解决即可

    展开全文
  • 目前我碰到的莫比乌斯适用样例如下所示: 1.与GCD一起出现,x 给定范围[1,b] ,y给定范围[1,d] 让你求有多少对这样的 (x,y)满足gcd(x,y)==k 解法:设一下 F(d)为 有多少对(x,y)满足gcd(x,y)== d 的倍数 ...
  • 文章目录YY的GCD能量采集[SDOI2014]数表[SDOI2017]数字表格[POI2007]ZAP-Queries[HAOI2011]Problem b[SDOI2015]约数个数和[CQOI2015]选数常见积性函数与迪利克雷卷积(用于杜教筛)简单的数学题 ...
  • 莫比乌斯题目结(上) BZOJ3994 大佬们推公式的手段是怎么学到的……qwq完全想不到啊qwq 学习的是这篇博客的推公式。 要点节选: 1.结论:d(i*j)是i*j的约数个数,则 2.又用到莫比乌斯函数的性质 3....
  • 首先是喜闻乐见的几个入门基础题,连题面基本都是一样的,流程是预处理mu函数,得到输入数据后整除分块(如果时间复杂度需要的话),思路主要是套用下图第二个公式: (截图来自电科bilibili上的算法讲堂大家可以...
  • 题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2190 算法讨论: 我们先来考虑一个点被看不到的情况是什么。假设我们在原点,现在有一个点(3,2), 和一个点(6,4),显示我们是可以看到(3,2)...
  • 莫比乌斯反演入门题目整除分块[洛谷P2568: GCD](https://www.luogu.org/problem/P2568)[SPOJ VLATTICE](https://www.spoj.com/problems/VLATTICE/en/)[hdu1695: GCD]...能量...
  • 莫比乌斯反演-题目

    2018-11-25 18:38:00
    莫比乌斯反演-题目  理论部分的证明实在太多了,而且很多题的做法就是个结论,如果全都放到理论部分看完后再说题不就没什么意思了吗?所以又单开了一篇题目:  理论上来说可能应该从易到难,但是有的题确实没...
  • 题目 【BZOJ2818】Gcd 【NOI2010】能量采集 \[ \begin{split} \sum_{x=1}^n\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)==x]&=\sum_{x=1}^n\sum_{d=1}^{\lfloor\frac nx \rfloor}\mu(d)\lfloor\frac n{xd}\rfloor\...
  • 莫比乌斯函数(下标是完全平方数,且是完全平方数的倍数是0,下标是素数是-1,下标是其他数是1) 未写 ,先贴上:来自 https://www.cnblogs.com/tpgzy/p/9433607.html luoguP2568 GCD luogu3455[POI2007]...
  • 莫比乌斯反演详解

    2019-10-01 05:20:04
    目录 莫比乌斯反演 莫比乌斯函数 狄利克雷卷积 反演 应用 练习题目 YY的gcd 约数个数和 后记 莫比乌斯反演 莫比乌斯函数 \(\mu(...
  • 莫比乌斯反演

    2021-03-15 16:06:16
    有的题目使用容斥原理做起来比较复杂,这时候可以使用莫比乌斯反演解决。 1.莫比乌斯函数的定义 x=p1α1p2α2…pkαk,pix = p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k},p_ix=p1α1​​p2α2​​…pkαk​​,...
  • 刚学会莫比乌斯反演,就去欢乐的切题啦,发现实在是肝不动,利用两天时间才肝了一下几道题. -----------by Gzy luoguP2568 GCD 链接: luoguP2568 && bzoj2818: GCD 题目描述 给定整数N,求1,y且Gcd(x,y)为素数的...
  • BZOJ 2693 jzptab 莫比乌斯反演 题目大意:给定n,m,求i从1到n,j从1到m,的i与j的最小公倍数之和。 这题真的是有问题,难想的一批,公式恐惧症无药可救患者。。。。。。 以下我们继续给出PoPoQQQ的PPT中的内容,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,301
精华内容 520
关键字:

莫比乌斯反演题目