HDU-5663 Hillan and the girl(莫比乌斯反演+分块)

Time Limit: 12000/6000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)

Problem Description

“WTF! While everyone has his girl(gay) friend, I only have my keyboard!” Tired of watching others’ affair, Hillan burst into scream, which made him decide not to hold it back. “All right, I am giving you a question. If you answer correctly, I will be your girl friend.” After listening to Hillan, Girl replied,

“What is the value of $\sum_{i=1}^n \sum_{j=1}^mf(i,j)$ , where f(i,j)=0 if gcd(i,j) is a square number and f(i,j)=1 if gcd(i,j) is not a square number(gcd(i,j) means the greatest common divisor of x and y)?” But Hillan didn’t have enough Intelligence Quotient to give the right answer. So he turn to you for help.

Input

The first line contains an integer T(1≤T≤10,000)——The number of the test cases. For each test case, the only line contains two integers n,m(1≤n,m≤10,000,000) with a white space separated.

Output

For each test case, the only line contains a integer that is the answer.

Sample Input

2

1 2333333

10 10

Sample Output

0 33

Hint

In the first test case, obviously $f\left(i,j\right)$ always equals to 0, because $i$ always equals to 1 and $\gcd\left(i,j\right)$ is always a square number(always equals to 1).

题意:

求n，m之间有多少对数满足gcd(i, j) 不是一个完全平方数。

思路:

莫比乌斯反演 + 分块

以下默认n< m;

我们令gcd(x, y) = k, k是完全平方数的时候g(k) = 1,否则g[k] = 0;

ans = \sum_{i=1}^n \sum_{j=1}^m[gcd(i,j)不是完全平方数]\\ = n \ast m - \sum_{i=1}^n \sum_{j=1}^m g(gcd[i,j] )\\ = n \ast m - \sum_{d=1}^n g(d) \sum_{i = 1}^{n/d} \sum_{j=1}^{m/d} [gcd(i,j) = 1]\\ 对于后面的部分,我们设f(x) 表示gcd(i, j) = x的数的对数。设F(x) 表示gcd(i, j) 是x 的倍数的数的个数。\\ F(x) = \sum_{x | d}f(d)\\ 由反演得到\\ f(x) = \sum_{x | d}\varphi(d/x)F(d)\\ = \sum_{x | d}\varphi(d/x) \ast \frac{n}{d} \ast \frac{m}{d}\\ ans = n \ast m - \sum_{d = 1}^{n}g(d) * f(1)\\ = n \ast m - \sum_{d = 1}^n g(d) \sum_{i = 1}^{n/d} \varphi(i) \ast \frac{n/d}{i} \frac{m/d}{i}\\ 那么我们令t = d \ast i\\ ans = n \ast m - \sum_{t=1}^n \frac{n}{t} \ast \frac{m}{t} \sum_{i | t} \varphi(i) * g(t/i)\\

然后后面的求和是可以预处理出来的，具体方法可以看代码，而前面的求和我们可以用分块去处理，这样这个东西的时间复杂度基本就已经降到可接受范围内了。

代码:

/*************************************************************************
    > File Name: HDU-5663.cpp
    > Author: wood
    > Mail: cbcruel@gmail.com
    > Created Time: 2018年08月03日 星期五 13时39分50秒
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<string>

using namespace std;
typedef long long LL;
#define sqr(x) (x)*(x)
const double eps = 1e-8;
const double C = 0.57721566490153286060651209;
const double pi = acos(-1.0);
const LL mod = 1e9 + 7;
const int maxn = 1e7 + 10;

int mu[maxn], pri[maxn], sum[maxn];
bool vis[maxn];
int cnt;

void Mobius(){
    cnt = 0;
    mu[1] = 1;
    for(int i = 2; i < maxn; ++i){
        if(!vis[i]){
            pri[++cnt] = i;
            mu[i] = -1;
         }for(int j = 1; j <= cnt; ++j){
             if(i * pri[j] >= maxn) break;
             vis[i * pri[j]] = true;
             if(i % pri[j]== 0){
                 mu[i * pri[j]] = 0;
                 break;
             }mu[i * pri[j]] = - mu[i];
        }
    }
    int t = sqrt(maxn);
    for(int i = 1; i <= t; ++i){
        int x = i * i;
        for(int j = x, k = 1; j < maxn; j+= x, ++k)
            sum[j] += mu[k];
    }for(int i = 1; i < maxn; ++i)
        sum[i] += sum[i-1];
}

LL solve(int b, int d){
    LL ans = 0, pos;
    for(int i = 1; i <= b; i = pos+1){
        pos = min(b/(b/i), d/(d/i));
        ans += 1LL * (b/i) * (d/i) * (sum[pos] - sum[i-1]);
    }return ans;
}

int main(){
    Mobius();
    int t;
    scanf("%d", &t);
    while(t--){
        int n, m;
        scanf("%d %d", &n, &m);
        LL ans = 1LL*n*m;
        if(n > m) swap(n, m);
        ans -= solve(n, m);
        printf("%lld\n", ans);
    }return 0;
}