Mophues
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 327670/327670 K (Java/Others)
Total Submission(s): 2824 Accepted Submission(s): 1215
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
Source 2013 ACM/ICPC Asia Regional Hangzhou Online
Recommend liuyiding 分析：显而易见，当p比较大时，ans一定是n*m，那么也就是log_2^(1e6)=20。 令num[i]表示i的素因子个数。
#include <bits/stdc++.h>
using namespace std;
long long num[500004],num1[500004];
long long sum[500004][20];
long long fac[24];
bool vis[500004];
long long c(int a,int b){
if(b<0)return 0;
if(a<b)return 0;
if(a==b)return 1;
return fac[a]/fac[b]/fac[a-b];
}
vector<int>prim;
int main(){
int t;
cin>>t;
fac[0]=1;
for (int i = 1; i < 15; ++i) {
fac[i]=fac[i-1]*i;
}
for (int i = 2; i < 500004; ++i) {
if(!vis[i]){
prim.push_back(i);
num[i]=1;
}
for (int j = 0; j < prim.size() && i*prim[j] < 500004; ++j) {
vis[i*prim[j]]=1;
num[i*prim[j]] = num[i]+1;
if(i%prim[j] == 0)break;
}
}
for (int i = 0; i < prim.size(); ++i) {
for (int j = prim[i]; j < 500004; j+=prim[i]) {
num1[j]++;
}
}
for (int i = 1; i <= 500004; ++i) {
for (int j = 0; j < 20; ++j) {
sum[i][j] = c(num1[i],j - num[i] + num1[i]);
if((num[i]-j)&1)sum[i][j]*=-1;
if(j)sum[i][j]+=sum[i][j-1];
}
}
for (int j = 0; j < 20; ++j) {
for (int i = 1; i <= 500004; ++i) {
sum[i][j] += sum[i-1][j];
}
}
while(t--){
int n,m,p;
scanf("%d%d%d",&n,&m,&p);
if(p >= 20){
printf("%lld\n",1LL*n*m);
continue;
}
if(n>m)swap(n,m);
long long ans = 0;
for (int l = 1,r; l <= n; l=r+1) {
r = min(n/(n/l),m/(m/l));
if (r >= n)r=n;
ans += 1LL*(n/l)*(m/l)*(sum[r][p] - sum[l-1][p]);
}
cout<<ans<<endl;
}
}