又是一道經(jīng)典題.

1.學(xué)習(xí)了下O(n) 的做法。

// // main.cpp // bzoj2154 // // Created by New_Life on 16/7/7. // Copyright ? 2016年 chenhuan001. All rights reserved. // #include <iostream> #include <string.h> #include <stdio.h> using namespace std;#define N 10001000 #define MOD 20101009//－－莫比烏斯反演函數(shù)－－// //說(shuō)明：利用線性素?cái)?shù)篩選順便求了個(gè)mu //注釋部分為求從區(qū)間[1,b]和區(qū)間[1,d]中取兩個(gè)數(shù)，互質(zhì)對(duì)數(shù)O（n^0.5） //復(fù)雜度:O(n) int mu[N]; long long sum[N]; int prime[N]; bool mark[N];void mobus() {int pcnt=0;memset(mark,0,sizeof(mark));mu[1] = 1;for(int i=2;i<N;i++){if(mark[i] == 0){prime[pcnt++] = i;mu[i] = -1;}for(int j=0;j<pcnt && i*prime[j]<N;j++){int tmp = i*prime[j];mark[tmp] = 1;if( i%prime[j] == 0 ){mu[tmp] = 0;break;}mu[tmp] = mu[i]*-1;}}for(int i=1;i<N;i++){sum[i] += sum[i-1]+(long long)mu[i]*i*i;sum[i] %= MOD;} }long long gaobili(long long b,long long d) {if(b<=0||d<=0) return 0;long long m = min(b,d);long long ans = 0;while(m>=1){long long tb = b/( b/m +1 )+1;long long td = d/( d/m +1 )+1;//前進(jìn)的最大位置long long tm = max(tb,td);ans += (sum[m]-sum[tm-1])*(((b/m+1)*(b/m)/2)%MOD)%MOD*(((d/m+1)*(d/m)/2)%MOD)%MOD ;ans %= MOD;m = tm-1;}return ans; } //等差數(shù)列求和模板，[a1,a1+d,...,an] long long allsum(long long a1,long long an,long long n) {if(n%2==0)return (a1+an)*(n/2);else return ((a1+an)/2)*n; }int main(int argc, const char * argv[]) {mobus();int b,d;while(scanf("%d%d",&b,&d)!=EOF){int m = min(b,d);long long ans = 0;while(m>=1){int tb = b/( b/m +1 )+1;int td = d/( d/m +1 )+1;//前進(jìn)的最大位置int tm = max(tb,td);ans += allsum(tm,m,m-tm+1)%MOD*gaobili(b/m, d/m)%MOD;ans %= MOD;m = tm-1;}cout<<(ans+MOD)%MOD<<endl;}return 0; } /*4 5*/

?

2.O(n)預(yù)處理，每次查詢n^0.5

因?yàn)閎zoj2693題目找不到了，所以直接用了這題來(lái)測(cè)試。

這題首先是一個(gè)經(jīng)典的公式變形。 交換連加時(shí)變量的位置。

而根據(jù)第二個(gè)重要的性質(zhì)，乘性函數(shù)的乘除之后還是乘性函數(shù)。（加減并不是）

所以后面的連加部分也是乘性函數(shù)，這時(shí)只需要的單獨(dú)看只含一個(gè)因子的時(shí)候，因?yàn)槔锩婧衭(i),所以對(duì)于D=x^k(x是素因子)只有當(dāng)i = 1 或 x 時(shí)不為0，所以

后面的為x^k(1-x)。這時(shí)可以在線性篩選時(shí)順便求出來(lái)。

**************************************************************Problem: 2154User: chenhuan001Language: C++Result: AcceptedTime:16668 msMemory:93088 kb ****************************************************************/#include <stdio.h> #include <string.h> #include <stdlib.h> #include <algorithm> #include <iostream> using namespace std; //－－莫比烏斯反演函數(shù)－－// //說(shuō)明：利用線性素?cái)?shù)篩選順便求了個(gè)mu //注釋部分為求從區(qū)間[1,b]和區(qū)間[1,d]中取兩個(gè)數(shù)，互質(zhì)對(duì)數(shù)O（n^0.5） //復(fù)雜度:O(n) #define N 10000010 bool mark[N]; int prime[N/10];long long sum[N];#define MOD 20101009void mobus() {int pcnt=0;sum[1] = 1;for(int i=2;i<N;i++){if(mark[i] == 0){prime[pcnt++] = i;sum[i] = (long long)i*(1-i)%MOD;}for(int j=0;j<pcnt && i*prime[j]<N;j++){int tmp = i*prime[j];mark[tmp] = 1;if( i%prime[j] == 0 ){sum[tmp] = sum[i]*prime[j];sum[tmp] %= MOD;break;}else{sum[tmp] = sum[i]*(sum[prime[j]])%MOD;}}}for(int i=1;i<N;i++)sum[i] = (sum[i]+sum[i-1])%MOD; }long long gaobili(int b,int d) {if(b<=0||d<=0) return 0;long long m = min(b,d);long long ans = 0;while(m>=1){long long tb = b/( b/m +1 )+1;long long td = d/( d/m +1 )+1;//前進(jìn)的最大位置long long tm = max(tb,td);ans += (sum[m]-sum[tm-1])*(((b/m+1)*(b/m)/2)%MOD)%MOD*(((d/m+1)*(d/m)/2)%MOD)%MOD;ans %= MOD;m = tm-1;}return (ans+MOD)%MOD; } int main() {mobus();int b,d;while(scanf("%d%d",&b,&d)!=EOF){printf("%d\n",(int)gaobili(b,d));}return 0; }

?

至此mobus大概都刷了一遍，原以為很復(fù)雜的東西，其實(shí)也不是很難。以后面對(duì)的題目可能有更多的公式變形，或許難在找出莫比烏斯模型。但基本的也就是這些方法了。

治好了多年的公式恐懼癥。。

?

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的bzoj2154(莫比乌斯反演)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。