题面
Sol
(ans=sum_{k=1}^{n}lfloorfrac{n}{k}
floorlfloorfrac{m}{k}
floorsum_{d|k}[f(d)<=p]mu(frac{k}{d}))
老套路了，不会推可以参看我写的其它题的题解
(其中f(d)表示d的素因数个数，可以在线性筛的时候处理出来)
(sum_{d|k}[f(d)<=p]mu(frac{k}{d}))筛不了，怎么办？
打表大法告诉我们(f(d)<=18)
18!!!
于是可以暴力记下这18个的前缀和，p大于等于18时输出(n*m)就好
# include <bits/stdc++.h>
# define RG register
# define IL inline
# define Zsydalao 666
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
const int _(5e5 + 1);
IL ll Read(){
char c = '%'; ll x = 0, z = 1;
for(; c > '9' || c < '0'; c = getchar()) if(c == '-') z = -1;
for(; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0';
return x * z;
}
int prime[_], num, mu[_], f[_], mx, s[20][_];
bool isprime[_];
IL void Prepare(){
isprime[1] = 1; mu[1] = 1;
for(RG int i = 2; i < _; ++i){
if(!isprime[i]) prime[++num] = i, mu[i] = -1, f[i] = 1;
for(RG int j = 1; j <= num && i * prime[j] < _; ++j){
isprime[i * prime[j]] = 1; f[i * prime[j]] = f[i] + 1;
if(i % prime[j]) mu[i * prime[j]] = -mu[i];
else{ mu[i * prime[j]] = 0; break; }
}
//mx = max(mx, f[i]);
}
//cout << mx << endl;
for(RG int i = 1; i < _; ++i)
for(RG int j = i; j < _; j += i) s[f[i]][j] += mu[j / i];
for(RG int i = 0; i <= 18; ++i)
for(RG int j = 1; j < _; ++j) s[i][j] += s[i][j - 1];
for(RG int i = 1; i <= 18; ++i)
for(RG int j = 1; j < _; ++j) s[i][j] += s[i - 1][j];
}
int main(RG int argc, RG char *argv[]){
Prepare();
for(RG int T = Read(); T; --T){
RG ll n = Read(), m = Read(), p = Read(), ans = 0;
if(n > m) swap(n, m);
if(p >= 18) ans = n * m;
else{
for(RG ll i = 1, j; i <= n; i = j + 1){
j = min(n / (n / i), m / (m / i));
ans += 1LL * (n / i) * (m / i) * (s[p][j] - s[p][i - 1]);
}
}
printf("%lld
", ans);
}
return 0;
}