题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4746
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 327670/327670 K (Java/Others)

Problem Description

As we know, any positive integer C ( C >= 2 ) can be written as the multiply of some prime numbers:
    C = p1×p2× p3× ... × pk
which p1, p2 ... pk are all prime numbers.For example, if C = 24, then:
    24 = 2 × 2 × 2 × 3
    here, p1 = p2 = p3 = 2, p4 = 3, k = 4

Given two integers P and C. if k<=P( k is the number of C's prime factors), we call C a lucky number of P.

Now, XXX needs to count the number of pairs (a, b), which 1<=a<=n , 1<=b<=m, and gcd(a,b) is a lucky number of a given P ( "gcd" means "greatest common divisor").

Please note that we define 1 as lucky number of any non-negative integers because 1 has no prime factor.

Input

The first line of input is an integer Q meaning that there are Q test cases.
Then Q lines follow, each line is a test case and each test case contains three non-negative numbers: n, m and P (n, m, P <= 5×105. Q <=5000).

Output

For each test case, print the number of pairs (a, b), which 1<=a<=n , 1<=b<=m, and gcd(a,b) is a lucky number of P.

Sample Input

2
10 10 0
10 10 1

Sample Output

63
93

Problem solving report:

Description: 1≤x,y≤n, 求gcd(x,y)分解后质因数个数小于等于k的(x,y)的对数。
Problem solving: 莫比乌斯反演。
设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，那么利用gcd(x,y)=k -> gcd(x/k,y/k)=1的性质可知：

但是这样肯定会超时。 
我们令a=p∗d，那么

我们就可以先获取每个a对应的，由于题目规定了最大的质因子数目，所以我们增加一维，设f[i][j]表示质因子数目小于等于j时前i项和，根据公式计算即可。最后我们再取个前缀和，使用分段优化就好了。

Accepted Code:

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 5;
bool isp[MAXN];
int res[MAXN], miu[MAXN], pre[MAXN], spt[MAXN][25];
void Mobius() {
    int cnt = 0;
    miu[1] = 1;
    for (int i = 2; i < MAXN; i++) {
        if (!isp[i]) {
            res[i] = 1;
            miu[i] = -1;
            pre[cnt++] = i;
        }
        for (int j = 0; j < cnt && i * pre[j] < MAXN; j++) {
            isp[i * pre[j]] = true;
            res[i * pre[j]] = res[i] + 1;
            if (i % pre[j])
                miu[i * pre[j]] = -miu[i];
            else {
                miu[i * pre[j]] = 0;
                break;
            }
        }
    }
    for (int i = 1; i < MAXN; i++)
        for (int j = i; j < MAXN; j += i)
            spt[j][res[i]] += miu[j / i];
    for (int i = 1; i < MAXN; i++)
        for (int j = 1; j < 20; j++)
            spt[i][j] += spt[i][j - 1];
    for (int i = 1; i < MAXN; i++)
        for (int j = 0; j < 20; j++)
            spt[i][j] += spt[i - 1][j];
}
int main() {
    Mobius();
    long long ans;
    int n, m, p, t, j;
    scanf("%d", &t);
    while (t--) {
        ans = 0;
        scanf("%d%d%d", &n, &m, &p);
        if (p >= 20) {
            printf("%lld\n", 1ll * n * m);
            continue;
        }
        if (n > m)
            swap(n, m);
        for (int i = 1; i <= n; i = j + 1) {
            j = min(n / (n / i), m / (m / i));
            ans += 1ll * (n / i) * (m / i) * (spt[j][p] - spt[i - 1][p]);
        }
        printf("%lld\n", ans);
    }
    return 0;
}