【bzoj3994】[SDOI2015]約數個數和 莫比烏斯反演

題目描述

設d(x)為x的約數個數，給定N、M，求 ?

輸入

輸入文件包含多組測試數據。

第一行，一個整數T，表示測試數據的組數。

接下來的T行，每行兩個整數N、M。

輸出

T行，每行一個整數，表示你所求的答案。

樣例輸入

2
7 4
5 6

樣例輸出

110
121

---

題解

莫比烏斯反演

根據 bzoj4176 推出的結論，

那么就有：

預處理mu及其前綴和。

由于要處理多組詢問，所以需要用O(n√n)的時間預處理出f，然后對于每組詢問分塊來求。

#include <cstdio>
#include <algorithm>
#define N 50010
using namespace std;
typedef long long ll;
const int n = 50000;
int mu[N] , sum[N] , prime[N] , tot , f[N];
bool np[N];
ll cal(int a , int b)
{int i , last;ll ans = 0;for(i = 1 ; i <= a && i <= b ; i = last + 1) last = min(a / (a / i) , b / (b / i)) , ans += (ll)(sum[last] - sum[i - 1]) * f[a / i] * f[b / i];return ans;
}
int main()
{int i , j , last , T , a , b;mu[1] = sum[1] = 1;for(i = 2 ; i <= n ; i ++ ){if(!np[i]) mu[i] = -1 , prime[++tot] = i;for(j = 1 ; j <= tot && i * prime[j] <= n ; j ++ ){np[i * prime[j]] = 1;if(i % prime[j] == 0){mu[i * prime[j]] = 0;break;}else mu[i * prime[j]] = -mu[i];}sum[i] = sum[i - 1] + mu[i];}for(i = 1 ; i <= n ; i ++ )for(j = 1 ; j <= i ; j = last + 1)last = i / (i / j) , f[i] += (last - j + 1) * (i / j);scanf("%d" , &T);while(T -- ) scanf("%d%d" , &a , &b) , printf("%lld\n" , cal(a , b));return 0;
}

?