数论初级魔法大赏

最近在准备关于莫比乌斯反演的课件,准备把例题简要整理下来,那就开始吧

1.bzoj 2190 [SDOI2008]仪仗队

最简单的做法,线性筛预处理出欧拉函数的前缀和,时间复杂度。

2.bzoj 2818 Gcd

其实就是,枚举所有质数后就是和上一道题一样做法了,双倍经验。

3.bzoj 2705 [SDOI2012]Longge的问题

变形一下,枚举每种gcd的值,即

那么根号枚举约数,单点求欧拉函数就做完了。

时间复杂度?是个经典的东西

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

求第个不含完全平方数因子的正整数

二分答案,转为求前个数中有多少数不含完全平方因子。容斥一下,总数减去是4(2的平方)的倍数的,减去9的倍数,16的倍数不用管,前面减过了,再减去25的倍数,加上36的倍数,因为前面多减了一次…那这样就发现了容斥系数就是莫比乌斯函数。时间复杂度

5.luogu P2257 YY的GCD(bzoj 2820)

求,组询问

bzoj 2818的加强版,把其中一个n换成了m,这样就不能用欧拉函数了,推导一下:

下述的表示质数

其中第三行莫比乌斯反演,第五行交换求和,第六行令,转而枚举,化简到最后用筛法预处理出所有的值即可,这里应该可以用线性筛,不过懒得推导的话也可以枚举所有质数再枚举它的倍数这样求,那么时间复杂度就和埃氏筛一样了,之后每次求一组询问就是经典的数论分块了。时间复杂度。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=10000000;
bool vis[N+5];
int prime[N+5],cnt;
int mu[N+5],f[N+5];
void getprime()
{
    mu[1]=1;
    for(int i=2;i<=N;i++)
    {
        if(!vis[i])
        {
            prime[cnt++]=i;
            mu[i]=-1;
        }
        for(int j=0;j<cnt && prime[j]<=N/i;j++)
        {
            vis[i*prime[j]]=true;
            if(i%prime[j]) mu[i*prime[j]]=-mu[i];
            else
            {
                mu[i*prime[j]]=0;
                break;
            }
        }
    }
    for(int i=0;i<cnt;++i)
    {
        int x=prime[i];
        for(int j=x;j<=N;j+=x)
            f[j]+=mu[j/x];
    }
    for(int i=1;i<=N;++i)
        f[i]+=f[i-1];
}
ll calc(int n,int m)
{
    if(n>m) swap(n,m);
    ll ans=0;
    for(int i=1,j;i<=n;i=j+1)
    {
        j=min(n/(n/i),m/(m/i));
        ans+=1LL*(f[j]-f[i-1])*(n/i)*(m/i);
    }
    return ans;
}
int main()
{
    getprime();
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        printf("%lld\n",calc(n,m));
    }
}

6.spoj LCMSUM

求,组询问。

这样线性筛预处理完,的求出函数值,每次回答即可。

7.bzoj 2154 Crash的数字表格

 

其中

一开始头铁,求的的值,超时无疑,然后学习了用线性筛求积性函数的思路。

线性筛过程分两种情况讨论

1.整除,那么枚举的约数时,如果关于的指数大于等于2的话莫比乌斯函数为零,对答案没有贡献,所以此时。

2.不整除,那么再分枚举的约数是否含有,不含有的部分就是,含的话,整体乘上这么多,并且莫比乌斯函数要变号,是。综上,此时。

这样这道题就做完了,时间复杂度。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=20101009;
const int N=10000000;
bool vis[N+5];
int prime[666666],cnt;
int f[N+5];
void getprime()
{
    f[1]=1;
    for(int i=2;i<=N;i++)
    {
        if(!vis[i])
        {
            prime[cnt++]=i;
            f[i]=(1-i+mod);
        }
        for(int j=0;j<cnt && i*prime[j]<=N;j++)
        {
            vis[i*prime[j]]=true;
            if(i%prime[j])
            {
                f[i*prime[j]]=1LL*(1-prime[j]+mod)*f[i]%mod;
            }
            else
            {
                f[i*prime[j]]=f[i];
                break;
            }
        }
    }
//    for(int i=1;i<=N;++i)
//    {
//        for(int j=i;j<=N;j+=i)
//        {
//            f[j]+=i*mu[i];
//            if(f[j]<0) f[j]+=mod;
//            else if(f[j]>=mod) f[j]-=mod;
//        }
//    }
}
int Sum(int n)
{
    return 1LL*(n+1)*n/2%mod;
}
int main()
{
    getprime();
    int n,m;
    scanf("%d%d",&n,&m);
    if(n<m) swap(n,m);
    ll ans=0;
    for(int i=1;i<=m;++i){
        ans+=1LL*i*Sum(n/i)%mod*Sum(m/i)%mod*f[i]%mod;
        if(ans>=mod) ans-=mod;
    }
    printf("%lld\n",ans);
}

8.bzoj 3994 [SDOI2015]约数个数和

求,组询问,其中是约数个数函数。

这个题一开始卡在一个结论上了,首先要知道,这个结论不好想,但可以用分解质因数的形式结合约数个数定理推出来,那解决了第一步,后面的就简单了。

至此又可以数论分块搞定单组询问了,时间复杂度。

9.bzoj 4659 lcm

化简下题意就是求,对取模,组询问。发现就是在第七题的基础上加了个多组询问,且只统计的。

那么前面的推导都是一样的,最后化简到

原式

头铁依然会TLE,还是先观察一下

是积性函数

且当分解质因数后的指数中有大于2的情况的话,显然此时,并且易知,这样又可以线性筛搞一搞了,然后预处理出的前缀和。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1<<30;
const int N=4000000;
bool vis[N+5];
int prime[N+5],cnt;
unsigned int f[N+5],sum[N+5];
void getprime() {
    f[1]=1;
    for(int i=2;i<=N;i++) {
        if(!vis[i]) {
            prime[cnt++]=i;
            f[i]=1U-i;
        }
        for(int j=0;j<cnt && i*prime[j]<=N;j++) {
            vis[i*prime[j]]=true;
            if(i%prime[j]) {
                f[i*prime[j]]=f[i]*f[prime[j]];
            }
            else {
                if(i==prime[j]) f[i*prime[j]]=-prime[j];
                else if(i/prime[j]%prime[j]==0) f[i*prime[j]]=0;
                else f[i*prime[j]]=f[i/prime[j]]*f[prime[j]*prime[j]];
                break;
            }
        }
    }
//    for(int i=1;i<=N;++i) {
//        for(int j=i;j<=N;j+=i) {
//            f[j]+=i*mu[i]*abs(mu[j/i]);
//        }
//    }
    for(int i=1;i<=N;++i)
        sum[i]=sum[i-1]+1U*i*f[i];
}
unsigned int Sum(int n)
{
    return 1LL*(n+1)*n/2;
}
int main()
{
    getprime();
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m;
        scanf("%d%d",&n,&m);
        if(n<m) swap(n,m);
        unsigned int ans=0;
        for(int i=1,j;i<=m;i=j+1){
            j=min(n/(n/i),m/(m/i));
            ans+=1U*(sum[j]-sum[i-1])*Sum(n/i)*Sum(m/i);
        }
        printf("%d\n",(int)(ans%mod));
    }
}

10.bzoj 4816 [Sdoi2017]数字表格

求,其中为斐波那契数列,结果模,组询问。

这样指数部分是关于的函数,可以分块,又因为外层是枚举的,所以分块套分块即可!时间复杂度,前一部分来源分析同第三题

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
#define N 1000000
bool vis[N+5];
int prime[N+5],cnt;
int mu[N+5],sum[N+5];
int f[N+5],pre[N+5];
void getprime() {
    mu[1]=1;
    for(int i=2;i<=N;i++) {
        if(!vis[i]) {
            prime[cnt++]=i;
            mu[i]=-1;
        }
        for(int j=0;j<cnt && prime[j]<=N/i;j++) {
            vis[i*prime[j]]=true;
            if(i%prime[j])
                mu[i*prime[j]]=-mu[i];
            else {
                mu[i*prime[j]]=0;
                break;
            }
        }
    }
    for(int i=1;i<=N;++i)
        sum[i]=sum[i-1]+mu[i];
}
int power(int x,ll n){
    int ans=1;
    while(n){
        if(n&1) ans=1LL*ans*x%mod;
        x=1LL*x*x%mod;
        n>>=1;
    }
    return ans;
}
ll calc(int n,int m,int d){
    ll ans=0;
    for(int i=1,j;i<=n;i=j+1){
        j=min(n/(n/i),m/(m/i));
        ans+=1LL*(sum[j]-sum[i-1])*(n/i)*(m/i);
    }
    return ans;
}
int main(){
    getprime();

    pre[0]=pre[1]=f[1]=1;
    for(int i=2;i<=N;++i){
        f[i]=f[i-1]+f[i-2];
        if(f[i]>=mod) f[i]-=mod;
        pre[i]=1LL*pre[i-1]*f[i]%mod;
    }
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m;
        scanf("%d%d",&n,&m);
        if(n>m) swap(n,m);
        int ans=1;
        for(int i=1,j;i<=n;i=j+1){
            j=min(n/(n/i),m/(m/i));
            int x=1LL*pre[j]*power(pre[i-1],mod-2)%mod;
            ll y=calc(n/i,m/i,i);
            ans=1LL*ans*power(x,y)%mod;
        }
        printf("%d\n",ans);
    }
}