Bzoj2694/Bzoj4659:莫比烏斯反演

先上題面:

首先看到這數據范圍顯然是反演了，然而第三個限制條件十分不可做。于是我們暫且無視他，大不了補集轉化算完再減是吧。

于是我們有:

這里我們定義:

于是這個東西我們可以nlogn篩的說。
也就是說，我們求出f的前綴和后，就可以O(sqrt(n)+sqrt(m))分塊計算了。
然而需要減去的東西怎么辦呢？
反演題最難的不是推公式，而是你推出了公式卻不知道是否可做。
仔細觀察以上兩個式子，原式中的g(也就是上式中的t)，不就是我們枚舉的gcd嗎?
題面要求兩個數不同時含某個平方因數，也就是他們的gcd不同時含某個平方因數。
那不就是我們原式中的g(上式中的t)不含平方因數嗎?
而一個數x含平方因數，會有什么性質呢?μ(x)=0!
所以我們先枚舉t，判斷其μ值非0，然后去枚舉h/t，更新f(h)即可。
這題取模2^30，我們直接用int自然溢出就好了。
(為什么?因為這樣加減乘顯然是對的，然而除法，只有在計算sum的時候會除二，這樣我們會損失一位的精度。而int的正數精度為取模2^31的，損失一位后正好夠用，所以我們可以這樣做。理論上取模2^31我們也可以用unsigned int做，然而取模2^32就必須long long了。以上內容純屬口胡，如果因此wa了別打我就是了QAQ……)

代碼:
(一開始sieve里面開的數組沒加static wa了一次，身敗名裂)

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define lli long long int 6 #define debug cout 7 using namespace std; 8 const int maxn=4e6+1e2,lim=4e6; 9 const int mod = 1 << 30; 10 11 int mu[maxn],f[maxn]; 12 13 inline void sieve() { 14 static int prime[maxn],cnt; 15 static bool vis[maxn]; 16 mu[1] = 1; 17 for(int i=2;i<=lim;i++) { 18 if( !vis[i] ) prime[++cnt] = i , mu[i] = -1; 19 for(int j=1;j<=cnt&&(lli)i*prime[j]<=lim;j++) { 20 const int tar = i * prime[j]; 21 vis[tar] = 1; 22 if( ! ( i % prime[j] ) ) break; 23 mu[tar] = -mu[i]; 24 } 25 } 26 for(int i=1;i<=lim;i++) if( mu[i] ) { 27 for(int j=1;(lli)i*j<=lim;j++) f[i*j] += j * mu[j]; 28 } 29 for(int i=1;i<=lim;i++) f[i] *= i , f[i] += f[i-1]; 30 } 31 inline int sum(int x) { 32 return x * ( x + 1 ) >> 1; 33 } 34 inline int calc(int n,int m) { 35 if( n > m ) swap(n,m); 36 int ret = 0; 37 for(int l=1,r;l<=n;l=r+1) { 38 r = min( n / ( n / l ) , m / ( m / l ) ); 39 ret += ( f[r] - f[l-1] ) * sum(n/l) * sum(m/l); 40 } 41 return ret; 42 } 43 44 int main() { 45 static int T,a,b; 46 static lli ans; 47 scanf("%d",&T) , sieve(); 48 while(T--) { 49 scanf("%d%d",&a,&b) , ans = calc(a,b); 50 ans = ( ans % mod + mod ) % mod; 51 printf("%lld\n",ans); 52 } 53 return 0; 54 } View Code

?

轉載于:https://www.cnblogs.com/Cmd2001/p/8522225.html

總結

以上是生活随笔為你收集整理的Bzoj2694/Bzoj4659:莫比乌斯反演的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。