几个经典的莫比乌斯反演练习题

先来一个莫比乌斯函数板子

1 int N = 10000000; 2 int not_prim[10000050],prim[10000050]; 3 long long mu[10000050],tot; 4 void getmu(long long n){ 5     not_prim[0] = not_prim[1] = 1; 6     mu[1] = 1; 7     for (long long i = 2 ; i<= n; i++){ 8         if (!not_prim[i]){ 9             mu[i] = -1;10             prim[++tot] = i;11         }12         for (long long j = 1; j <= tot && prim[j]*i <= n ; j++){13             not_prim[prim[j]*i] = i;14             if (i % prim[j] == 0){15                 mu[prim[j]*i] = 0;16                 break;17             }18             mu[prim[j]*i] =-mu[i];19         }20     }21 }

几个例题

BZOJ2154

#include 
      
       const long long mod = 20101009;const double ex = 1e-10;#define inf 0x3f3f3f3fusing namespace std;int T;int N = 10000000;int not_prim[10000050],prim[10000050];long long mu[10000050],tot;long long sum_mu[10000050];void getmu(long long n){    not_prim[0] = not_prim[1] = 1;    mu[1] = 1;    for (long long i = 2 ; i<= n; i++){        if (!not_prim[i]){            mu[i] = -1;            prim[++tot] = i;        }        for (long long j = 1; j <= tot && prim[j]*i <= n ; j++){            not_prim[prim[j]*i] = i;            if (i % prim[j] == 0){                mu[prim[j]*i] = 0;                break;            }            mu[prim[j]*i] =-mu[i];        }    }    for (int i = 1 ; i <= n ; i++){        sum_mu[i] = (sum_mu[i-1] + (mu[i] * i * i  % mod) + mod ) % mod;    }}inline long long sum(long long m,long long n){    return ((m*(m+1)/2LL) % mod) * ((n*(n+1)/2LL) % mod) % mod;}inline long long F(long long m,long long n){    if (n > m) swap(n,m);    long long nex;    long long ans = 0;    for (long long i = 1LL;i<=n; i = nex + 1LL){        nex = min(n/(n/i),m/(m/i));        long long tmp1 = ( (sum_mu[nex] - sum_mu[i-1])  % mod + mod ) % mod;        ans = (ans + ( sum(m/i,n/i) * tmp1 % mod ) )% mod;    }    return ans;}long long solve(long long n,long long m){    long long ans = 0;    if (n > m) swap(n,m);    long long nex;    for (long long i = 1 ; i<=n ; i = nex+1){        nex = min(m/(m/i),n/(n/i));        long long tmp = ((i+nex)*(nex-i+1LL)/2LL) % mod;        ans = (ans + (tmp * F(n/i,m/i)) % mod) % mod;    }    return ans;}int main(){    long long m,n;    scanf("%lld%lld",&m,&n);    getmu(min(n,m));    printf("%lld\n",solve(m,n));}
      

BZOJ2301

#include 
      
       const long long mod = 1e9+7;const double ex = 1e-10;#define inf 0x3f3f3f3fusing namespace std;int not_prim[200050],prim[200050],mu[200050],tot,sum_mu[200050];long long x;void getmu(int n){    not_prim[0] = not_prim[1] = 1;    mu[1] = 1;    for (int i = 2 ; i<= n; i++){        if (!not_prim[i]){            mu[i] = -1;            prim[++tot] = i;        }        for (int j = 1; j <= tot && prim[j]*i <= n ; j++){            not_prim[prim[j]*i] = i;            if (i % prim[j] == 0){                mu[prim[j]*i] = 0;                break;            }            mu[prim[j]*i] =-mu[i];        }    }    for (int i = 1 ; i <= n ; i++){        sum_mu[i] = sum_mu[i-1] + mu[i];    }}int solve(int n,int m,int x){    int ans = 0;    int nex;    if (n>m) swap(n,m);    for (int i = 1 ; i*x<=n ; i = nex+1){        nex = min(n/(n/(i*x)),m/(m/(i*x)))/x;        ans += (n/(i*x)) * (m/(i*x)) * (sum_mu[nex] - sum_mu[i-1]);    }    return ans;}int main(){    int T;    cin >> T;    getmu(50050);    while (T--){        int a,b,c,d,k;        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);        int ans = solve(b,d,k) - solve(a-1,d,k) - solve(b,c-1,k) + solve(a-1,c-1,k);        printf("%d\n",ans);    }}
      

BZOJ2440

#include 
      
       const long long mod = 1e9+7;const double ex = 1e-10;#define inf 0x3f3f3f3fusing namespace std;int not_prim[200050],prim[2000050],mu[2000050],tot;long long x;void getmu(int n){    not_prim[0] = not_prim[1] = 1;    mu[1] = 1;    for (int i = 2 ; i<= n; i++){        if (!not_prim[i]){            mu[i] = -1;            prim[++tot] = i;        }        for (int j = 1; j <= tot && prim[j]*i <= n ; j++){            not_prim[prim[j]*i] = i;            if (i % prim[j] == 0){                mu[prim[j]*i] = 0;                break;            }            mu[prim[j]*i] =-mu[i];        }    }}bool check(long long mid){    long long ans = mid;    for (long long i = 2 ; i * i <= mid ;i++ ){        ans += mu[i]*(mid/(i*i));    }    return ans >= x;}int main(){    int T;    scanf("%d",&T);    getmu(200000);    while (T--){        scanf("%I64d",&x);        long long r = 1;        long long l = 1e10;        long long ans = 1;        while (r <= l){            long long mid = ( r + l ) >> 1;            if (check(mid)){                ans = mid;                l = mid - 1;            }            else r = mid + 1;        }        printf("%lld\n",ans);    }    return 0;}
      

BZOJ2820

#include 
      
       const long long mod = 1e9+7;const double ex = 1e-10;#define inf 0x3f3f3f3fusing namespace std;long long not_prim[10000050],prim[10000050],mu[10000050],tot;void getmu(long long n){    not_prim[0] = not_prim[1] = 1LL;    mu[1] = 1LL;    for (long long i = 2LL ; i<= n; i++){        if (!not_prim[i]){            mu[i] = -1;            prim[++tot] = i;        }        for (long long j = 1; j <= tot && prim[j]*i <= n ; j++){            not_prim[prim[j]*i] = i;            if (i % prim[j] == 0LL){                mu[prim[j]*i] = 0LL;                break;            }            mu[prim[j]*i] =-mu[i];        }    }}long long c[10000050];void init(long long n){    for (long long i = 1; i<=tot ;i++){        for (long long j = prim[i] ; j <= n; j+=prim[i]){            c[j] += mu[j/prim[i]];        }    }    for (long long i = 1 ; i<=n; i++)        c[i] += c[i-1];}long long solve(long long n,long long m){    long long ans = 0;    long long nex;    if (n>m) swap(n,m);    for (long long i = 1; i<=n ; i=nex+1){        nex = min(n/(n/i),m/(m/i));        ans += (n/i)*(m/i)*(c[nex]-c[i-1]);    }    return ans;}int main(){    int T;    scanf("%d",&T);    getmu(10000001);    init(10000001);    while (T--){        long long n,m;        scanf("%lld%lld",&n,&m);        printf("%lld\n",solve(n,m));    }}
      

BZOJ3529

#include 
      
       const unsigned int mod = 1LL<<31;const double ex = 1e-10;#define inf 0x3f3f3f3fusing namespace std;int T;int N = 100000;int not_prim[100050],prim[100050],mu[100050],tot;void getmu(int n){    not_prim[0] = not_prim[1] = 1LL;    mu[1] = 1LL;    for (int i = 2LL ; i<= n; i++){        if (!not_prim[i]){            mu[i] = -1;            prim[++tot] = i;        }        for (int j = 1; j <= tot && prim[j]*i <= n ; j++){            not_prim[prim[j]*i] = i;            if (i % prim[j] == 0LL){                mu[prim[j]*i] = 0LL;                break;            }            mu[prim[j]*i] =-mu[i];        }    }}struct node{    int i;    unsigned int fi;}F[100050];unsigned int c[100050];int lowbit(int k){    return k&(-k);}void Modify(int num,unsigned int v){    while (num<=N){        c[num]= c[num] + v ;        num+=lowbit(num);    }}unsigned int Sum(int num){    long long ans = 0;    while (num != 0){        ans=ans + c[num];        num-=lowbit(num);    }    return ans;}void initF(int n){    for (int i = 1; i<=n ; i++){        for (int j = i; j<=n; j+=i){            F[j].fi=F[j].fi + i;        }        F[i].i = i;    }}struct quer{    int n,m;    int a;    int id;    unsigned int ans;}Q[20022];inline bool cmpa(quer a,quer b){    return a.a < b.a;}inline bool cmpid(quer a,quer b){    return a.id < b.id;}inline bool cmp(node a,node b){    return a.fi < b.fi;}void solve(int n){    sort(Q+1,Q+T+1,cmpa);    sort(F+1,F+N+1,cmp);    int j = 0;    for (int i = 1; i<=T; i++){        while (j+1<=n&&F[j+1].fi<=Q[i].a){            j++;            for (int k = F[j].i ; k<=n ; k+=F[j].i){                Modify(k,F[j].fi * mu[k/F[j].i]);            }        }        int n,m;        n=Q[i].n;        m=Q[i].m;        if (n > m ) swap(m,n);        int nex;        unsigned int ans = 0;        for (int k = 1; k<=n; k = nex+1){            nex = min(n/(n/k),m/(m/k));            ans = ans + (n/k) * (m/k)  * (Sum(nex) - Sum(k-1));        }        Q[i].ans = ans;    }    sort(Q+1,Q+T+1,cmpid);}int main(){    getmu(100000);    initF(100000);    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;    solve(100000);    for (int i = 1; i<=T; i++){        printf("%d\n",Q[i].ans%mod);    }    return 0;}
      

BZOJ2693

1 #include 
      
         2 const int mod = 100000009;  3 const double ex = 1e-10;  4 #define inf 0x3f3f3f3f  5 using namespace std;  6 int N = 10000000;  7 int not_prim[10000050],prim[10000050];  8 int mu[10000050],tot;  9 int pre[10000050]; 10 namespace fastIO{ 11     #define BUF_SIZE 100000 12     #define OUT_SIZE 100000 13     #define ll long long 14     //fread->read 15     bool IOerror=0; 16     inline char nc(){ 17         static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE; 18         if (p1==pend){ 19             p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin); 20             if (pend==p1){IOerror=1;return -1;} 21             //{printf("IO error!\n");system("pause");for (;;);exit(0);} 22         } 23         return *p1++; 24     } 25     inline bool blank(char ch){
    return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';} 26     inline int read(int &x){ 27         bool sign=0; char ch=nc(); x=0; 28         for (;blank(ch);ch=nc()); 29         if (IOerror)return 0; 30         if (ch=='-')sign=1,ch=nc(); 31         for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0'; 32         if (sign)x=-x; 33         return 1; 34     } 35     inline int read(ll &x){ 36         bool sign=0; char ch=nc(); x=0; 37         for (;blank(ch);ch=nc()); 38         if (IOerror)return 0; 39         if (ch=='-')sign=1,ch=nc(); 40         for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0'; 41         if (sign)x=-x; 42         return 1; 43     } 44     inline int read(double &x){ 45         bool sign=0; char ch=nc(); x=0; 46         for (;blank(ch);ch=nc()); 47         if (IOerror)return 0; 48         if (ch=='-')sign=1,ch=nc(); 49         for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0'; 50         if (ch=='.'){ 51             double tmp=1; ch=nc(); 52             for (;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0'); 53         } 54         if (sign)x=-x; 55         return 1; 56     } 57     inline int read(char *s){ 58         char ch=nc(); 59         for (;blank(ch);ch=nc()); 60         if (IOerror)return 0; 61         for (;!blank(ch)&&!IOerror;ch=nc())*s++=ch; 62         *s=0; 63         return 1; 64     } 65     inline void read(char &c){ 66         for (c=nc();blank(c);c=nc()); 67         if (IOerror){c=-1;return;} 68     } 69     //fwrite->write 70     struct Ostream_fwrite{ 71         char *buf,*p1,*pend; 72         Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;} 73         void out(char ch){ 74             if (p1==pend){ 75                 fwrite(buf,1,BUF_SIZE,stdout);p1=buf; 76             } 77             *p1++=ch; 78         } 79         void print(int x){ 80             static char s[15],*s1;s1=s; 81             if (!x)*s1++='0';if (x<0)out('-'),x=-x; 82             while(x)*s1++=x%10+'0',x/=10; 83             while(s1--!=s)out(*s1); 84         } 85         void println(int x){ 86             static char s[15],*s1;s1=s; 87             if (!x)*s1++='0';if (x<0)out('-'),x=-x; 88             while(x)*s1++=x%10+'0',x/=10; 89             while(s1--!=s)out(*s1); out('\n'); 90         } 91         void print(ll x){ 92             static char s[25],*s1;s1=s; 93             if (!x)*s1++='0';if (x<0)out('-'),x=-x; 94             while(x)*s1++=x%10+'0',x/=10; 95             while(s1--!=s)out(*s1); 96         } 97         void println(ll x){ 98             static char s[25],*s1;s1=s; 99             if (!x)*s1++='0';if (x<0)out('-'),x=-x;100             while(x)*s1++=x%10+'0',x/=10;101             while(s1--!=s)out(*s1); out('\n');102         }103         void print(double x,int y){104             static ll mul[]={
    1,10,100,1000,10000,100000,1000000,10000000,100000000,105                 1000000000,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL,106                 100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL};107             if (x<-1e-12)out('-'),x=-x;x*=mul[y];108             ll x1=(ll)floor(x); if (x-floor(x)>=0.5)++x1;109             ll x2=x1/mul[y],x3=x1-x2*mul[y]; print(x2);110             if (y>0){
    out('.'); for (size_t i=1;i
       
        
          m) swap(n,m);167     int nex;168     int ans = 0;169     for (long long i = 1 ; i <= n ; i = nex+1){170         nex = min(n/(n/i),m/(m/i));171         ans = (ans + (int)(( sum(n/i,m/i) * (long long)(pre[nex] - pre[i-1] + mod) ) % mod)  ) % mod;172     }173     return ans;174 }175 int main()176 {177 178     int T;179     scanf("%d",&T);180     getmu(N);181     getpre(N);182     while (T--){183         long long n,m;184         read(n);185         read(m);186         print(solve(n,m));187         print('\n');188     }189     return 0;190 }