题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4746Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 327670/327670 K (Java/Others)
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.
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).
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.
2 10 10 0 10 10 1
63 93
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; }