几个经典的莫比乌斯反演练习题
先来一个莫比乌斯函数板子
1 int N = 10000000; 2 int not_prim[10000050],prim[10000050]; 3 long long mu[10000050],tot; 4 void getmu(long long n){ 5not_prim[0] = not_prim[1] = 1; 6mu[1] = 1; 7for (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 <bits/stdc++.h>const long long mod = 1009;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));}
View Code
BZOJ2301
#include <bits/stdc++.h>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);}}
View Code
BZOJ2440
#include <bits/stdc++.h>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;}
View Code
BZOJ2820
#include <bits/stdc++.h>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));}}
View Code
BZOJ3529
#include <bits/stdc++.h>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;}
View Code
BZOJ2693
1 #include <bits/stdc++.h> 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 15bool IOerror=0; 16inline 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} 25inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';} 26inline 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} 35inline 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} 44inline 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} 57inline 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} 65inline void read(char &c){ 66 for (c=nc();blank(c);c=nc()); 67 if (IOerror){c=-1;return;} 68} 69//fwrite->write 70struct 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<y&&x3*mul[i]<mul[y];out('0'),++i); print(x3);}111 }112 void println(double x,int y){print(x,y);out('\n');}113 void print(char *s){while (*s)out(*s++);}114 void println(char *s){while (*s)out(*s++);out('\n');}115 void flush(){if (p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}}116 ~Ostream_fwrite(){flush();}117}Ostream;118inline void print(int x){Ostream.print(x);}119inline void println(int x){Ostream.println(x);}120inline void print(char x){Ostream.out(x);}121inline void println(char x){Ostream.out(x);Ostream.out('\n');}122inline void print(ll x){Ostream.print(x);}123inline void println(ll x){Ostream.println(x);}124inline void print(double x,int y){Ostream.print(x,y);}125inline void println(double x,int y){Ostream.println(x,y);}126inline void print(char *s){Ostream.print(s);}127inline void println(char *s){Ostream.println(s);}128inline void println(){Ostream.out('\n');}129inline void flush(){Ostream.flush();}130 };131 using namespace fastIO;132 133 inline void getmu(int n){134not_prim[0] = not_prim[1] = 1;135mu[1] = 1;136for (int i = 2 ; i<= n; i++){137 if (!not_prim[i]){138 mu[i] = -1;139 prim[++tot] = i;140 }141 for (int j = 1; j <= tot && prim[j]*i <= n ; j++){142 not_prim[prim[j]*i] = i;143 if (i % prim[j] == 0){144 mu[prim[j]*i] = 0;145 break;146 }147 mu[prim[j]*i] =-mu[i];148 }149}150 }151 inline void getpre(int n){152for (int i = 1; i<=n ;i++){153 if (mu[i]==0) continue;154 for (long long j = i ; j<=n ; j+=i){155 pre[j] = (pre[j] + mu[i] * i + mod) % mod;156 }157}158for (int i = 1; i<=n ;i++){159 pre[i] = ( pre[i-1] + (int)((long long)pre[i]*(long long)i % mod ) ) % mod;160}161 }162 inline long long sum(long long m,long long n){163return ((m*(m+1)/2LL) % mod) * ((n*(n+1)/2LL) % mod) % mod;164 }165 inline int solve(int n,int m){166if (n > m) swap(n,m);167int nex;168int ans = 0;169for (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}173return ans;174 }175 int main()176 {177 178int T;179scanf("%d",&T);180getmu(N);181getpre(N);182while (T--){183 long long n,m;184 read(n);185 read(m);186 print(solve(n,m));187 print('\n');188}189return 0;190 }
卡常数。
