Description
神犇YY虐完數(shù)論后給kAc出了一題:
給定求
且
為質(zhì)數(shù)的
有多少對(duì)即硼。
kAc不想做脾歧，并把這道題扔給了你砾淌。
Input Format
Output Format
Sample Input
2
10 10
100 100
Sample Output
30
2971
Constraints
對(duì)于%的數(shù)據(jù)悬嗓，
谁撼。
CCYOS
我的第二道莫比烏斯反演題。
本題即計(jì)算
設(shè)為
且
為
的
的個(gè)數(shù)镶骗，
代入原式
設(shè)
為
且
為
和
的倍數(shù)的
的個(gè)數(shù)桶现，
莫比烏斯反演的第二種形式，
代入原式
令
再次令
code
#include<bits/stdc++.h>
using namespace std;
#define mxn 10000005
int T,N,M,cnt;
int prime[mxn],vis[mxn],done[mxn];
long long sum[mxn],mu[mxn];
inline int read(){
int ret = 0,fl = 1;
char c = getchar();
for(;!isdigit(c)&&c != '-';c = getchar())if(c == '-')fl = 0;
for(;isdigit(c);c = getchar())ret = (ret << 3) + (ret << 1) + c - 48;
return fl ? ret : -ret;
}
inline void get_mu(int n){
mu[1] = 1;
for(int i = 2;i <= n;++i){
if(!vis[i])prime[++cnt] = i,mu[i] = -1;
for(int j = 1;j <= cnt&&prime[j] * i<= n;++j){
vis[i * prime[j]] = 1;
if(!(i % prime[j]))break;
else mu[i * prime[j]] = -mu[i];
}
}
for(int j = 1;j <= cnt;++j)
for(int i = 1;i * prime[j] <= n;++i)
done[i * prime[j]] += mu[i];//儲(chǔ)存處理完后的mu[i]
for(int i = 1;i <= n;++i)
sum[i] = 1ll * (sum[i - 1] + done[i]);
}
int main(){
T = read();
get_mu(10000000);
for(int i = 1;i <= T;++i){
N = read();M = read();
int limit = min(N,M);
long long ans = 0;
for(int l = 1,r;l <= limit;l = r + 1){
r = min(N/(N/l),M/(M/l));
ans += 1ll * (N/l) * (M/l) * (sum[r] - sum[l - 1]);//long long
}
printf("%lld\n",ans);
}
return 0;
}
