精华内容
下载资源
问答
  • 1.3.1 为什么使用函数 14 1.3.2 函数的类型 14 1.3.3 函数的参数 15 1.3.4 在公式中输入函数 16 1.4 在公式中使用名称 18 1.4.1 名称的作用范围 19 1.4.2 命名区域 19 1.4.3 命名公式 20 1.4.4 命名常量 21...
  • 如果一个正整数m的所有小于m的不同因子(包括1)加起来正好等于m本身,那么就被称它为完全数。它是指这样的一些特殊的自然数,它所有的真因子(即除了自身以外的...那么问题来了,为什么我的代码有毛病呢? 大神赐教
  • 由于楼主是个小蒟蒻,...当n不等于1时,n所有因子的莫比乌斯函数值的和为0 也就是说 ∑d∣nμ(d)={1n=10n>1\sum_{d|n}\mu(d)= \begin{cases} 1&amp

    由于楼主是个小蒟蒻,所以理解的很慢,所以就很详细
    然后学习的时候看了很多大佬的博客,yyb,wfy…还有一堆不认识的emmm,wzw巨佬的讲解,然后终于理解了那么一点,就来记录一下
    (表示打这么多公式是真的累…)
    公式打的比较多,如果有那些地方写错了希望各位大佬能指出,我一定及时的改正
    至于代码…码风应该还不错吧(至少我觉得还是很好看的
    因为我正在慢慢学,所以也就在慢慢更新(速度应该还凑合,但毕竟天天考试时间也不算太多)
    在前面的题目中证明需要用到的一些玄学小学奥数的东西的证明写在了最后(因为放在前面好难排版捂脸



    莫比乌斯函数简介

    首先先介绍一下什么是莫比乌斯函数

    (转自百度百科)

    莫比乌斯函数是一个数论函数,它同时也是一个积性函数(μ(ab) =μ(a)μ(b), a,b互质)
    当n不等于1时,n所有因子的莫比乌斯函数值的和为0

    也就是说
    dnμ(d)={1n=10n>1\sum_{d|n}\mu(d)= \begin{cases} 1& \text{n=1}\\ 0& \text{n>1} \end{cases}

    莫比乌斯函数完整定义的通俗表达:
    1)莫比乌斯函数μ(n)的定义域是N
    2)μ(1)=1
    3)当n存在平方因子时,μ(n)=0
    4)当n是素数或奇数个不同素数之积时,μ(n)=-1
    5)当n是偶数个不同素数之积时,μ(n)=1

    μ(n)={1n=0(1)kn= p1*p2*p3...pk0其他\mu(n)= \begin{cases} 1& \text{n=0}\\ (-1)^k& \text{n= p1*p2*p3...pk}\\ 0& \text{其他} \end{cases}


    其实上面的都没有什么特别大的用处

    莫比乌斯反演的公式

    接着我们看莫比乌斯反演

    g(n)=dnf(d)设 g(n)=\sum_{d|n}f(d)

    \Updownarrow

    f(n)=dnμ(d)g(nd)f(n)=\sum_{d|n}\mu(d)g\left(\frac{n}{d}\right)
    g(n)=ndf(d)g(n)=\sum_{n|d}f(d)

    \Updownarrow

    f(n)=ndg(d)μ(dn)f(n)=\sum_{n|d}g(d)\mu\left(\frac{d}{n}\right)
    df(注意这个 d 一般就是 f 的定义域或者说是“函数值有效”的定义域)

    表示这两个式子的整除来整除去让我这个没学过小学奥数的小蒟蒻看的头都是大的,天天搞不清楚谁整除谁…
    有了上面的式子的恒等互换似乎依旧没有什么用


    板子题及证明

    于是我们来看一下最基本的题目的证明

    板子

    i=1nj1m[gcd(i,j)==1]求\sum_{i=1}^n\sum_{j-1}^m[gcd(i,j)==1]
    [gcd(i,j)==1]gcd1ans++这里的[gcd(i,j)==1]是是否满足gcd为1,如果是就ans++

    首先我们把它化作一般形
    f(x)=i=1nj1m[gcd(i,j)==x]设f(x)=\sum_{i=1}^n\sum_{j-1}^m[gcd(i,j)==x]

    g(n)=ndf(d)g(n)=\sum_{n|d}f(d)

    \Updownarrow

    f(n)=ndg(d)μ(dn)f(n)=\sum_{n|d}g(d)\mu\left(\frac{d}{n}\right)
    g(n)那么,我们的g(n)是什么呢

    直接按照定义把它带进去,可以化出这么一个式子
    g(x)=i=1nj=1m[xgcd(i,j)]g(x)=\sum_{i=1}^n\sum_{j=1}^m[x|gcd(i,j)]

    x\Downarrow 把x提出来

    g(x)=i=1nxj=1mx[1gcd(i,j)]g(x)=\sum_{i=1}^{{\lfloor\frac{n}{x}\rfloor}}\sum_{j=1}^{\lfloor\frac{m}{x}\rfloor}[1|gcd(i,j)]
    gcd1i,j这个时候,由于所有的gcd肯定可以整除1,所以,这个式子的值就变成了i,j的个数
    g(x)=nxmxg(x)=\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{x}\rfloor
    g(x)然后,我们再把g(x)带回原来的式子里面,可以得到
    f(x)=xdg(d)μ(dx)=xdμ(dx)ndmdf(x)=\sum_{x|d}g(d)\mu\left(\frac{d}{x}\right)=\sum_{x|d}\mu\left(\frac{d}{x}\right)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor

    f(1)=1dμ(d1)ndmd=d=1min(n,m)μ(d)ndmdf(1)=\sum_{1|d}\mu\left(\frac{d}{1}\right)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor=\sum_{d=1}^{min(n,m)}\mu({d})\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor
    Ans=d=1min(n,m)μ(d)ndmdAns=\sum_{d=1}^{min(n,m)}\mu({d})\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor
    O(n)算到了这里,我们就可以用O(n)来快速的求了


    接下来我们来看一下稍微的一点变式
    i=1nj=1m[gcd(i,j)==d]求 \sum_{i=1}^n\sum_{j=1}^m [ gcd(i,j)==d ]
    f(x)=i=1nj=1m[gcd(i,j)=x]令 f(x)=\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=x]

    \Downarrow

    g(x)=xdf(d)=i=1nj=1m[xgcd(i,j)]g(x)=\sum_{x|d}f(d)=\sum_{i=1}^n\sum_{j=1}^m[x|gcd(i,j)]
    [xgcd(i,j)]\because[x|gcd(i,j)]

    xixj\therefore x|i\text{且}x|j
    g(x)=i=1nj=1m[xgcd(i,j)]=i=1nxj=1mx=nxmxg(x)=\sum_{i=1}^n\sum_{j=1}^m[x|gcd(i,j)]=\sum_{i=1}^{\lfloor\frac{n}{x}\rfloor}\sum_{j=1}^{\lfloor\frac{m} {x}\rfloor}=\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{x}\rfloor
    f(x)=xdg(d)μ(dx)=xdμ(dx)ndmdf(x)=\sum_{x|d}g(d)\mu\left(\frac{d}{x}\right)=\sum_{x|d}\mu\left(\frac{d}{x}\right)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor
    xdμ(dx)ndmd=i=1nxμ(i)nixmix=i=1nxμ(i)nximxi\sum_{x|d}\mu\left(\frac{d}{x}\right)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor=\sum_{i=1}^{\lfloor\frac{n}{x}\rfloor}\mu(i)\lfloor\frac{n}{ix}\rfloor\lfloor\frac{m}{ix}\rfloor=\sum_{i=1}^{\lfloor\frac{n}{x}\rfloor}\mu(i)\frac{\lfloor\frac{n}{x}\rfloor}{i}\frac{\lfloor\frac{m}{x}\rfloor}{i}
    然而,(上面的真的看不懂)这个题目还有一种更加感性的证明:
    i=1nj=1m[gcd(i,j)==d]\sum_{i=1}^n\sum_{j=1}^m [ gcd(i,j)==d ]

    i=1nxj=1mx[gcd(i,j)==1]\sum_{i=1}^{\lfloor\frac{n}{x}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{x}\rfloor}[gcd(i,j)==1]
    nxmxab由于\lfloor\frac{n}{x}\rfloor和\lfloor\frac{m}{x}\rfloor看的不顺眼,我们把它换成a,b

    i=1aj1b[gcd(i,j)==1]于是又变成了\sum_{i=1}^a\sum_{j-1}^b[gcd(i,j)==1]

    我们开心的发现这个和上面长得一样,把结论愉快的搬过来
    Ans=i=1nxμ(i)nximxi于是Ans=\sum_{i=1}^{\lfloor\frac{n}{x}\rfloor}\mu(i)\frac{\lfloor\frac{n}{x}\rfloor}{i}\frac{\lfloor\frac{m}{x}\rfloor}{i}
    这种证明比上面的复杂的数学友好多了

    +O(n)到了这一步,只需要运用 数论分块+前缀和优化进行处理,把复杂度降到O\left(\sqrt{n}\right)


    于是我们直接来看板子题

    POI2007 ZAP-Queries

    题意:i=1nj=1m[gcd(i,j)==d]求 \sum_{i=1}^n\sum_{j=1}^m [ gcd(i,j)==d ]
    那么久不扯太多了,上面都是讲解,直接来扯代码实现吧

    • 运用线性筛把μ\mu给晒出来并求前缀和
    • 运用我们推出来的一大长串的式子直接带进去运用数论分块的优秀算法把复杂度降到n\sqrt{n}

    所以,我们总得时间复杂度是O(n+Tn)O\left(n+T\sqrt{n}\right)

    #include <algorithm>
    #include <iostream>
    #include <cstring>
    #include <cstdio>
    using namespace std;
    #define re register
    #define gc getchar()
    #define ll long long
    inline int read()
    {
    	re int x(0); re char ch(gc);
    	while(ch>'9'||ch<'0') ch=gc;
    	while(ch>='0'&&ch<='9') x=(x*10)+(ch^48),ch=gc;
    	return x;
    }
    const int N=50050;
    int mu[N],pri[N],sum[N],vis[N],cnt;
    void get_mu(int n)	//线性筛求mu函数
    {
    	mu[1]=1;
    	for(int i=2;i<=n;++i)
    	{
    		if(!vis[i])
    			mu[i]=-1,pri[++cnt]=i;
    		for(int j=1;j<=cnt&&i*pri[j]<=n;++j)
    		{
    			vis[i*pri[j]]=1;
    			if(i%pri[j]==0) break;
    			else mu[i*pri[j]]=-mu[i];
    		}
    	}
    	for(int i=1;i<=n;++i) sum[i]=sum[i-1]+mu[i];	//处理前缀和
    }
    void work()
    {
    	int a=read(),b=read(),d=read();
    	int n=min(a,b),ans=0;
    	for(int l=1,r;l<=n;l=r+1)	//数论分块优化
    	{
    		r=min(a/(a/l),b/(b/l));
    		ans+=(a/(l*d))*(b/(l*d))*(sum[r]-sum[l-1]);
    	}
    	cout<<ans<<endl;
    }
    int main()
    {
    	int T=read();
    	get_mu(50050);
    	while(T--) work();
    	return 0;
    }
    

    我们来看这个板子的稍微升级一点的一个题目

    Problem B

    题意
    i=abj=cd[gcd(i,j)==k]求\sum_{i=a}^b\sum_{j=c}^d [ gcd(i,j)==k ]
    对于这个题目,我们可以运用一下容斥原理
    f(n,m)=i=1nj=1m[gcd(i,j)==d]记f(n,m)=\sum_{i=1}^n\sum_{j=1}^m [ gcd(i,j)==d ]
    那么运用容斥原理,我们可以把答案表示成这样:

    ans=f(b,d)f(a1,d)f(b,c1)+f(a1,c1) ans=f(b,d)-f(a-1,d)-f(b,c-1)+f(a-1,c-1)
    f(a,b)然后把f(a,b)化回去

    由于莫比乌斯反演的常见套路(模板),我们得知
    f(n,m)=i=1min(nx,mx)μ(i)nximxif(n,m)=\sum_{i=1}^{min(\lfloor\frac{n}{x}\rfloor,\lfloor\frac{m}{x}\rfloor)}\mu(i)\frac{\lfloor\frac{n}{x}\rfloor}{i}\frac{\lfloor\frac{m}{x}\rfloor}{i}
    于是就可以愉快的把这些套进整个板子里,由于有数论分块,整个的复杂度是n\sqrt{n}

    #include <algorithm>
    #include <iostream>
    #include <cstring>
    #include <cstdio>
    using namespace std;
    #define re register
    #define gc getchar()
    #define ll long long
    inline int read()
    {
    	re int x(0); re char ch(gc);
    	while(ch>'9'||ch<'0') ch=gc;
    	while(ch>='0'&&ch<='9') x=(x*10)+(ch^48),ch=gc;
    	return x;
    }
    const int N=50050;
    int mu[N],pri[N],sum[N],vis[N],cnt;
    void get_mu(int n)
    {
    	mu[1]=1;
    	for(int i=2;i<=n;++i)
    	{
    		if(!vis[i])
    			mu[i]=-1,pri[++cnt]=i;
    		for(int j=1;j<=cnt&&i*pri[j]<=n;++j)
    		{
    			vis[i*pri[j]]=1;
    			if(i%pri[j]==0) break;
    			else mu[i*pri[j]]=-mu[i];
    		}
    	}
    	for(int i=1;i<=n;++i) sum[i]=sum[i-1]+mu[i];
    }
    int F(int a,int b,int d)
    {
    	int n=min(a,b),ans=0;
    	for(int l=1,r;l<=n;l=r+1)
    	{
    		r=min(a/(a/l),b/(b/l));
    		ans+=(a/(l*d))*(b/(l*d))*(sum[r]-sum[l-1]);
    	}
    	return ans;
    }
    void work()
    {
    	int a=read(),b=read(),c=read(),d=read(),k=read();
    	int ans=F(b,d,k)-F(a-1,d,k)-F(b,c-1,k)+F(a-1,c-1,k);	//容斥
    	cout<<ans<<endl;
    }
    int main()
    {
    	int T=read();
    	get_mu(50050);
    	while(T--) work();
    	return 0;
    }
    

    稍微带一点变式的经典入门题目

    接下来就是稍微带一点变式的反演题目了


    约数个数和

    i=1nj=1md(ij)[d(x)x]求\sum_{i=1}^n\sum_{j=1}^m d(ij) [d(x)表示x的约数个数]
    d(ij)首先,我们要知道如何去求d(ij),有这么一个式子

    d(ij)=xiyj[gcd(i,j)==1]d(ij)=\sum_{x|i}\sum_{y|j}[gcd(i,j)==1]
    i=1nj=1mxiyj[gcd(i,j)==1]于是,我们的式子就变成了要求\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}[gcd(i,j)==1]
    xy改变求和顺序,先枚举因数 x 和 y

    x=1ny=1mnxmy[gcd(x,y)==1]于是我们得到了\sum_{x=1}^n\sum_{y=1}^m \lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor[gcd(x,y)==1]
    到了这一步,我们就可以开始上莫比乌斯反演了

    f(x)=i=1nj=1mnimj[gcd(i,j)==x]设f(x)=\sum_{i=1}^n\sum_{j=1}^m \lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{j}\rfloor[gcd(i,j)==x]

    g(n)=ndf(d)g(n)=\sum_{n|d}f(d)
    g(x)=i=1nj=1mnimj[xgcd(i,j)]于是g(x)=\sum_{i=1}^n\sum_{j=1}^m \lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{j}\rfloor[x|gcd(i,j)]

    xgcd同样我们把x提出来消除gcd,于是我们得到

    g(x)=i=1nxj=1mxnixmjxg(x)=\sum_{i=1}^{\lfloor\frac{n}{x}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{x}\rfloor} \lfloor\frac{n}{ix}\rfloor\lfloor\frac{m}{jx}\rfloor
    g(x)把g(x)带回原来的式子

    f(n)=ndg(d)μ(dn)f(n)=\sum_{n|d}g(d)\mu\left(\frac{d}{n}\right)
    f(1)=1dg(d)μ(d)=d=1min(n,m)μ(d)i=1ndj=1mdnidmjdf(1)=\sum_{1|d}g(d)\mu\left(d\right)=\sum_{d=1}^{min(n,m)}\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
    nidy到了这一步之后我们发现,由于 \lfloor\frac{n}{id}\rfloor和枚举y没什么关系,于是又可以把它提前

    d=1min(n,m)μ(d)i=1ndnidj=1mdmjd\sum_{d=1}^{min(n,m)}\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
    这个复杂的长的很的式子看得十分难受,于是我们就记

    p=nidq=mjdp=\lfloor\frac{n}{id}\rfloor,q=\lfloor\frac{m}{jd}\rfloor

    于是两个就是很明显的数论分块了,算出来之后再合并起来
    Ans=d=1min(n,m)μ(d)pqAns=\sum_{d=1}^{min(n,m)}\mu({d})*p*q

    到这里,就完全推完了,整个的复杂度就是nn=n\sqrt{n}*\sqrt{n}=n

    于是上一波代码

    #include <algorithm>
    #include <iostream>
    #include <cstring>
    #include <cstdio>
    using namespace std;
    #define re register
    #define gc getchar()
    #define ll long long
    inline int read()
    {
    	re int x(0); re char ch(gc);
    	while(ch>'9'||ch<'0') ch=gc;
    	while(ch>='0'&&ch<='9') x=(x*10)+(ch^48),ch=gc;
    	return x;
    }
    const int N=5e4+10;
    int mu[N],pri[N],f[N],vis[N],cnt;
    void get_mu(int n)	//线性筛求mu函数
    {
    	mu[1]=1;
    	n-=5;
    	for(int i=2;i<=n;++i)
    	{
    		if(!vis[i])
    			mu[i]=-1,pri[++cnt]=i;
    		for(int j=1;j<=cnt&&i*pri[j]<=n;++j)
    		{
    			vis[i*pri[j]]=1;
    			if(i%pri[j]==0) 
    			{
    				mu[i*pri[j]]=0;
    				break;
    			}
    			else 
    				mu[i*pri[j]]=-mu[i];
    		}
    	}
    	for(int i=1;i<=n;++i)
    		mu[i]+=mu[i-1];
    	for(int x=1;x<=n;++x)
    	{
    		ll res=0;
            for(int l=1,r;l<=x;l=r+1) 
    			r=x/(x/l),res+=1LL*(r-l+1)*(x/l);
    		f[x]=res;
    	}
    }
    void work()
    {
    	int a=read(),b=read();
    	int n=min(a,b);
    	ll ans=0;
    	for(int l=1,r;l<=n;l=r+1)	//数论分块优化
    	{
    		r=min(a/(a/l),b/(b/l));
            ans+=1LL*(mu[r]-mu[l-1])*f[a/l]*f[b/l];
    	}
    	cout<<ans<<endl;
    }
    int main()
    {
    	int T=read();
    	get_mu(N);
    	while(T--) work();
    	return 0;
    }
    

    YY的GCD

    i=1nj=im[gcd(i,j)==k](kprima)求\sum_{i=1}^n\sum_{j=i}^m [ gcd(i,j)==k ](k\in{prima})
    ()根据莫比乌斯反演的常见套路(上面的各种结论),我们可以很容易地化到这一步:
    kprimad=1min(n,m)μ(d)nkdmkd\sum_{k\in{prima}} \sum_{d=1}^{min(n,m)} \mu(d) *\frac{n}{kd}*\frac{m}{kd}
    (Tnlogn)TLE由于这样的枚举最后复杂度是(T\sqrt{n}logn),肯定会TLE,我们需要考虑如何去优化
    T=kd设T=kd
    Ans=kprimad=1min(n,m)μ(d)nTmTAns=\sum_{k\in{prima}} \sum_{d=1}^{min(n,m)} \mu(d) *\frac{n}{T}*\frac{m}{T}

    =T=1min(n,m)nTmTkTμ(Tk)=\sum_{T=1}^{min(n,m)}\frac{n}{T}\frac{m}{T} \sum_{k|T}\mu(\frac{T}{k})
    然后后面的kTμ(Tk)\sum_{k|T}\mu(\frac{T}{k})部分是可以预处理前缀和的,所以整个的复杂度就降到了TnT\sqrt{n}

    接着我们来上一下代码:

    #include <algorithm>
    #include <iostream>
    #include <cstring>
    #include <cstdio>
    using namespace std;
    #define re register
    #define gc getchar()
    #define ll long long
    inline int read()
    {
    	re int x(0); re char ch(gc);
    	while(ch>'9'||ch<'0') ch=gc;
    	while(ch>='0'&&ch<='9') x=(x*10)+(ch^48),ch=gc;
    	return x;
    }
    const int N=1e7+10;
    int mu[N],pri[N],sum[N],vis[N],cnt,f[N];
    void get_mu(int n)	//线性筛求mu函数
    {
    	mu[1]=1;
    	n-=5;
    	for(int i=2;i<=n;++i)
    	{
    		if(!vis[i])
    			mu[i]=-1,pri[++cnt]=i,f[i]=1;
    		for(int j=1;j<=cnt&&i*pri[j]<=n;++j)
    		{
    			vis[i*pri[j]]=1;
    			if(i%pri[j]==0) 
    			{
    				f[i*pri[j]]=mu[i];
    				mu[i*pri[j]]=0;
    				break;
    			}
    			else 
    				f[i*pri[j]]=-f[i]+mu[i],mu[i*pri[j]]=-mu[i];
    		}
    		f[i]+=f[i-1];
    	}
    }
    void work()
    {
    	int a=read(),b=read();
    	int n=min(a,b);
    	ll ans=0;
    	for(int l=1,r;l<=n;l=r+1)	//数论分块优化
    	{
    		r=min(a/(a/l),b/(b/l));
            ans+=1LL*(f[r]-f[l-1])*(a/l)*(b/l);
    	}
    	cout<<ans<<endl;
    }
    int main()
    {
    	int T=read();
    	get_mu(N);
    	while(T--) work();
    	return 0;
    }
    

    有了上面的那个题目的铺垫,我们来看接下来这个题目

    简单的数学题

    (i=1nj=1mijgcd(i,j))modp求\Big(\sum_{i=1}^n\sum_{j=1}^m i*j* gcd(i,j)\Big) mod p
    gcd(i,j)为了靠近莫比乌斯反演模型,先枚举gcd(i,j)的值,把它单独提出来,于是原式就变成了

    k=1nki=1nj=1mij[gcd(i,j)==k]\sum_{k=1}^nk\sum_{i=1}^n\sum_{j=1}^m i*j* [ gcd(i,j)==k ]
    k把k提出来:

    k=1nki=1nkj=1mkk2ij[gcd(i,j)==1]=k=1nk3i=1nkj=1mkij[gcd(i,j)==1]\sum_{k=1}^nk\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor} k^2*i*j* [ gcd(i,j)==1]=\sum_{k=1}^nk^3\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor} i*j* [ gcd(i,j)==1]
    到了这里就是很明显的一波莫比乌斯反演了,由于看的不爽,我们记

    a=nkb=mka=\lfloor\frac{n}{k}\rfloor,b=\lfloor\frac{m}{k}\rfloor
    上莫比乌斯反演

    f(x)=i=1aj=1bij[gcd(i,j)==x]设f(x)=\sum_{i=1}^a\sum_{j=1}^b i*j* [gcd(i,j)==x]

    g(n)=ndf(d)g(n)=\sum_{n|d}f(d)
    g(x)=i=1aj=1bij[xgcd(i,j)]于是g(x)=\sum_{i=1}^a\sum_{j=1}^b i*j[x|gcd(i,j)]

    g(x)=x2i=1axj=1bxijg(x)=x^2\sum_{i=1}^{\lfloor\frac{a}{x}\rfloor}\sum_{j=1}^{\lfloor\frac{b}{x}\rfloor} i*j
    根据各种小学奥数的芝士(没学过小学奥数的小蒟蒻表示捂脸走开)

    i=1aj=1bij=a(a+1)2b(b+1)2我们可以知道\sum_{i=1}^{a&#x27;}\sum_{j=1}^{b&#x27;} i*j=\frac{a&#x27;(a&#x27;+1)}{2}*\frac{b&#x27;(b&#x27;+1)}{2}

    便S(a,b)=a(a+1)2b(b+1)2为了方便表示,我们记S(a&#x27;,b&#x27;)=\frac{a&#x27;(a&#x27;+1)}{2}*\frac{b&#x27;(b&#x27;+1)}{2}
    g(x)=x2S(ax,bx)于是g(x)=x^2S\Big(\lfloor\frac{a}{x}\rfloor,\lfloor\frac{b}{x}\rfloor\Big)
    g(x)f(x)这个时候把g(x)带回到f(x)中

    f(k)=d=1min(a,b)d2μ(d)S(ax,bx)f(k)=\sum_{d=1}^{min(a,b)}d^2*\mu(d)*S\Big(\lfloor\frac{a}{x}\rfloor,\lfloor\frac{b}{x}\rfloor\Big)
    然后再带回到最开始的式子

    Ans=k=1min(n,m)k3d=1min(nk,mk)d2μ(d)S(nkd,mkd)Ans=\sum_{k=1}^{min(n,m)}k^3\sum_{d=1}^{min(\lfloor\frac{n}{k}\rfloor,\lfloor\frac{m}{k}\rfloor)}d^2*\mu(d)*S\Big(\lfloor\frac{n}{kd}\rfloor,\lfloor\frac{m}{kd}\rfloor\Big)
    n=m然后这里的情况非常简单,因为n=m,所以就开可以继续化简

    QAQ然而算了那么久其实是为后面的题准备的QAQ
    Ans=k=1nk3d=1nkd2μ(d)nkd2(1+bkd)2nkd2所以,Ans=\sum_{k=1}^nk^3\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor}d^2*\mu(d)*\frac{\lfloor\frac{n}{kd}\rfloor^2(1+\lfloor\frac{b}{kd}\rfloor)^2}{\lfloor\frac{n}{kd}\rfloor^2}
    算到了这里,莫比乌斯函数的部分都结束了,我们来看后面的处理——杜教筛


    上述证明涉及到的各种东西的证明补充

    (由于我还比较弱,有的地方证明可能还不算太严密,但是比较感性好理解

    莫比乌斯反演的证明

    g(n)=dnf(d)设 g(n)=\sum_{d|n}f(d)

    \Updownarrow

    f(n)=dnμ(d)g(nd)f(n)=\sum_{d|n}\mu(d)g\left(\frac{n}{d}\right)

    证明:
    (fg)(n)=dnf(d)g(nd)\because(f*g)(n)=\sum_{d|n}f(d)g\left(\frac{n}{d}\right)

    g(n)=dnf(d)=fI\therefore g(n)=\sum_{d|n}f(d)=f*I
    μ两边都卷一个\mu

    gμ=fIμ\Rightarrow g*\mu=f*I*\mu

    μI=dnμ(d)=[n=1]\because\mu*I=\sum_{d|n}\mu(d)=[n=1]

    只有nd=1d=n的时候有值。\because\text{只有$\frac{n}{d}=1$即$d=n$的时候有值。}

    f[n=1]=f\therefore f*[n=1]=f

    gμ=f[n=1]=f\therefore g*\mu=f*[n=1]=f
    :把这个狄利克雷卷积展开即可得到:
    f(n)=dnμ(d)g(nd)f(n)=\sum_{d|n}\mu(d)g\left(\frac{n}{d}\right)

    上面是一段非常严谨的证明,但也是有稍微感性一点的理解方式:

    展开全文
  • LINGO软件的学习

    2009-08-08 22:36:50
    2.1 为什么使用集 集是LINGO建模语言的基础,是程序设计最强有力的基本构件。借助于集,能够用一个单一的、长的、简明的复合公式表示一系列相似的约束,从而可以快速方便地表达规模较大的模型。 2.2 什么是集 集是...
  • 我写了两个递归程序,一个是错的,一个是对的,我不明白错的为什么错了,因为思路和正确的代码是一样的,求大神解答。 --------------------------------------以下是正确的------------------------------- #...
  • excel的使用

    2012-11-25 17:06:01
    再比如,公式: =if(SUM(A1:A5>0SUM(A1:A5),0) 此式就利用了嵌套函数,意思是,当A1至A5的和大于0时,返回这个值,如果小于0,那么就返回0。 还有一点要提醒你注意:以上的符号均半角,而且IF与括号之间...
  • clear all; I=imread('E:\Desktop\Walking\img\0001.jpg'); figure(1);imshow(I); %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%... 另外为什么Y算出来的是偏差值,和meanshift公式不一样啊
  • 《数据结构 1800题》

    热门讨论 2012-12-27 16:52:03
    10.在下面的程序段中,对x的赋值语句的频度__t(n)=O(n3)____(表示 n的函数) FOR i:=1 TO n DO FOR j:=1 TO i DO FOR k:=1 TO j DO x:=x+delta; 【北京工业大学 1999 一、6(2分)】 ...
  • 为什么其它群的话单正常,唯独11群不正常呢?11群是四个群中最小的群,其中继计次表位于缓冲区的首位,打完电话后查询内存发现出中继群号在内存中是正确的,取完话单后再查就不正确了。 结 论: 话单池的一个备份...
  • c++ 面试题 总结

    2009-09-16 08:44:40
    为什么? int n; if (n == 10) // 第一种判断方式 if (10 == n) // 第二种判断方式 如果少了个=号,编译时就会报错,减少了出错的可能行,可以检测出是否少了= -------------------------------------------------...
  • 数据结构(C++)有关练习题

    热门讨论 2008-01-02 11:27:18
    请编写一个函数将这个线性表原地逆置,即将数组的前n个原地址内容置换(en-1,en-2,…,e3,e2,e1,e0)。 2、 针对带附加头结点的单链表,试编写下列函数: A. 定位函数Locate:在单链表中寻找第i个结点。若找到...
  • MySQL命令大全

    2018-01-15 11:19:17
    例如,往表 MyClass中插入二条记录, 这二条记录表示:编号的名Tom的成绩.45, 编号 的名Joan 的成绩.99,编号 的名Wang 的成绩.5. mysql>insert into MyClass values(1,’Tom’,96.45),(2,’Joan...
  • MYSQL常用命令大全

    2011-05-30 13:31:24
    例如,往表 MyClass中插入二条记录, 这二条记录表示:编号1的名Tom的成绩96.45, 编号2 的名Joan 的成绩82.99,编号3 的名Wang 的成绩96.5. mysql> insert into MyClass values(1,'Tom',96.45),(2,...
  • “%”可以代表任意长度的字符串,长度可以为0; “_”只能表示单个字符。 如果要匹配姓张且名字只有两个字的人的记录,“张”字后面必须要有两个“_”符号。因为一个汉字是两个字符,而一个“_”符号只能代表一个字符...
  • 第三章 Sql查询与函数 一、 SQL概述 SQL(Structured Query Language)结构化查询语言,是一种数据库查询和程序设计语言,用于存取数据以及查询、更新和管理关系数据库系统。同时也是数据库脚本文件的扩展名。  SQL...
  • 2009达内SQL学习笔记

    2010-02-10 19:46:58
    --把提成是空值的转化为0 DISTINCT:过滤重复 把重复的行过滤掉;多个字段组合时,只排除组合重复的。 DISTINCT必须使用列名,不能使用计算或者表达式。 所有的聚合函数都可以使用。如果指定列名,则DISTINCT...
  • SQL语法大全

    2014-03-30 11:00:11
    Recordset对象Open方法的CursorType参数表示将以什么样的游标类型启动数据,包括adOpenForwardOnly、adOpenKeyset、adOpenDynamic及adOpenStatic,分述如下: ----------------------------------------------------...
  • 数学基础研究基本数学概念(数、几何形状、集合、函数...),及其 如何构成更复杂结构和概念的 层次结构,特别是一类 也被称为元数学概念的 基础性重要结构,用它们来形成数学语言(公式、理论、以及它们的 用来表意...
  • select type,sum(case vender when 'A' then pcs else 0 end),sum(case vender when 'C' then pcs else 0 end),sum(case vender when 'B' then pcs else 0 end) FROM tablename group by type  显示结果: type ...
  • oracle数据库经典题目

    2011-02-17 15:05:20
    13.填写下面的语句,使其可以Class表的ID列添加一个名PK_CLASS_ID的主键约束。 ALTER TABLE Class Add ____________ PK_LASS_ID (Constraint) PRIMARY KEY ________ (ID) 14. 每个Oracle 10g数据库在创建后都...
  • 请大侠们来帮看看,为什么最后的优化部分,不管我设初值为多少,优化的结果还是等于初值%利用移动最小二乘法(MLS)拟和一组点pi的直线,直线L1形式为:l*x+m*y-D=0%即求 min( sum (-D)^2*thet(||pi-q||) )%pi是一组点...

    请大侠们来帮看看,为什么最后的优化部分,不管我设初值为多少,优化的结果还是等于初值

    %利用移动最小二乘法(MLS)拟和一组点pi的直线,直线L1形式为:l*x+m*y-D=0

    %即求 min( sum (-D)^2*thet(||pi-q||) )

    %pi是一组点,thet函数是移动最小二乘法中的权重函数,采用高斯函数形式,q点是pi点的均值点R在拟和的直线上的投影

    %n={l_norm,m_norm}, 直线L1: l*x+m*y-D=0 的法向量, D是待求未知量

    %n1={k_norm,1} 与直线L1垂直的直线L2: k*x-y-(k*r_x-r_y)=0 的法向量 ,直线L2过均值点R(r_x,r_y)

    % n*n1=0

    %数据准备

    %PI =

    %  -18.4466   -5.6646

    %  -18.0146   -5.4918

    %R =

    %  -18.2306   -5.5782

    %%%%%%%%%%%%%%%%%%%%%%%%%%%程序主体%%%%%%%%%%%%%%%%%%%%%%%%%%%

    clear all

    syms l_norm m_norm k_norm D_line x y Q11 Q12

    %求直线L1的法向量

    m_norm=solve('l_norm^2+m_norm^2=1','m_norm');

    % m_norm有2个值,为了简化问题,只考虑其中第一个值

    norm1=[l_norm,m_norm(1,1)];

    %已知的一组点pi

    PI =[-18.4466 -5.6646

    -18.0146 -5.4918];

    %pi的均值点 R(r_x,r_y)

    R =[-18.2306,-5.5782];

    %pi的个数

    [b_R,n_R]=size(PI);%pi的个数

    %求直线L2的法向量

    k_norm=solve('l_norm*k_norm+m_norm=0','k_norm');%直线L1与直线L2相互垂直,n*n1=0

    k_norm=subs(k_norm,{'l_norm','m_norm'},{l_norm,m_norm(1,1)});

    solution=solve('l_norm*x+m_norm*y-D_line=0','k_norm*x-y-(k_norm*r_x-r_y)=0');

    %求R点在直线L1上的投影Q

    Q=[Q11,Q12];

    Q11=subs(solution.x,{'k_norm','m_norm','r_x','r_y'},{k_norm,m_norm(1,1),R(1,1),R(1,2)});

    Q12=subs(solution.y,{'k_norm','m_norm','r_x','r_y'},{k_norm,m_norm(1,1),R(1,1),R(1,2)});

    %初始化优化函数myfun_MLS

    myfun_MLS=0;

    h=2;%thet函数的初始值

    for j=1:b_R

    ff_MLS=(dot(norm1,PI(j,:))-D_line)^2;

    thet=exp(-((PI(j,1)-Q11)^2+(PI(j,2)-Q12)^2)^2/h^2);

    myfun_MLS=myfun_MLS+ff_MLS*thet;

    end

    myfun_MLS=vectorize(myfun_MLS);

    myfun_MLS=strrep(myfun_MLS,'l_norm','x(1)');

    myfun_MLS=strrep(myfun_MLS,'D_line','x(2)');

    myfun_MLS

    %优化函数初始值

    x0=[1,1];

    %采用标准算法,解无约束非线性优化问题

    options=optimset('Display','iter','TolFun',1e-18,'GradObj','on');

    [x,fval,exitflag,output]=fminsearch(myfun_MLS,x0,options);

    x %%%%%%%%%%%%%% %就是这里,x还是等于初值

    展开全文

空空如也

空空如也

1 2
收藏数 25
精华内容 10
关键字:

为什么sum函数等于0