题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=4746

题意：

1≤x,y≤n , 求gcd(x,y)分解后质因数个数小于等k的(x,y)的对数。

分析：

莫比乌斯反演。

还是一个套路，我们设

f(d)：满足gcd(x,y)=d且x,y均在给定范围内的(x,y)的对数。

F(d)：满足d|gcd(x,y)且x,y均在给定范围内的(x,y)的对数。

显然F(x)=[n/x]∗[m/x]，反演后我们得到

最直接的方法，枚举质数p，那么

这样肯定会超时。

我们令a=p∗d，那么

我们希望快速获得每个a对应的∑p|aμ(a/p)，由于题目规定了最大的质因子数目，所以我们增加一维，设f[i][j]表示质因子数目小于等于j时 前i项和，根据公式计算即可。

最后我们再取个前缀和就好了。注意这里仍然使用了分段优化。

代码：

/*

-- Hdu 4746

-- Created by jiangyuzhu

-- 2016/5/30

*/

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <cmath>

#include <stack>

using namespace std;

typedef long long ll;

#define sa(n) scanf("%d", &(n))

#define sal(n) scanf("%I64d", &(n))

#define pl(x) cout << #x << " " << x << endl

#define mdzz cout<<"mdzz"<<endl;

const int maxn = 5e5 + 5 ;

int tot = 0;

int miu[maxn], prime[maxn], f[maxn][20 + 5];

int cnt[maxn];

bool flag[maxn];

void mobius()

{

    miu[1] = 1;

    tot = 0;

    for(int i = 2; i < maxn; i++){

        if(!flag[i]){

            prime[tot++] = i;

            miu[i] = -1;

            cnt[i] = 1;

        }

        for(int j = 0; j < tot && i * prime[j] < maxn; j++){

            flag[i * prime[j]] = true;

            cnt[i * prime[j]] = cnt[i] + 1;

            if(i % prime[j]){

                miu[i * prime[j]] = -miu[i];

            }

            else{

                miu[i * prime[j]] = 0;

                break;

            }

        }

    }

    for(int i = 1; i < maxn; i++){

        for(int j = i; j < maxn; j += i){

            f[j][cnt[i]] += miu[j / i];

        }

    }

    for(int i = 1; i < maxn; i++){

        for(int j = 1; j < 20; j++){

            f[i][j] +=  f[i][j - 1] ;

        }

    }

    //前缀和

    for(int i = 1; i < maxn; i++){

        for(int j = 0; j < 20; j++){

            f[i][j] += f[i - 1][j];

        }

    }

}

int main (void)

{

    mobius();

    int T;sa(T);

    int n, m, k;

    for(int kas = 1; kas <= T; kas++){

       scanf("%d%d%d", &n, &m, &k);

       ll ans = 0;

       k = min(k, 19);

       int j;

       if(n > m) swap(n, m);

       for(int i = 1; i <= n; i = j + 1){

           j = min(n /(n / i), m / (m / i ));

          ans += (n / j) * 1ll * (m / j) * (f[j][k] - f[i - 1][k]);

       }

       printf("%lld\n", ans);

    }

    return 0;

}