题意描述：
求 (displaystylesum_{i=1}^{n}sum_{j=1}^{m} [gcd(i,j) in prime]), (Tleq 10^4, n,mleq 10^7)
solution：
反演进阶题。
先枚举一下 (p) 可得：
(displaystylesum_{pin prime}sum_{i=1}^{n}sum_{j=1}^{m} [gcd(i,j) == p])
由
可得：
(displaystylesum_{pin prime}sum_{i=1}^{n}sum_{j=1}^{m} sum_{dmid i,dmid j} mu(d))
先枚举一下 (d) 可得：
(displaystylesum_{pin prime}sum_{d=1}^{nover d} mu(d) sum_{i=1}^{nover d}sum_{j=1}^{mover d} [gcd(i,j) == 1])
(=displaystylesum_{pin prime}sum_{d=1}^{nover d}mu(d) {nover dp} {mover dp})
(dp) 化 (Q) 可得：
(displaystylesum_{Q=1}^{n} {nover Q} {mover Q}sum_{pmid Q,pin prime} mu({Qover p}))
然后我们就可以直接把 (displaystyle F(Q) = sum_{pmid Q,pin prime} mu({Qover p}))，给求出来。
考虑枚举每个质因数 (p) ,那么 (p) 只会对他的倍数有贡献。这样的复杂度就降为 (O(nlnn)) 的了。
剩下的部分整除分块即可。
总的时间复杂度为 (O(Tsqrt(n) + nlnn)) (大力吸氧就过了)
Code
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
const int N = 1e7+10;
int T,n,m,tot;
int prime[N],mu[N],ans[N];
bool check[N];
inline int read()
{
int s = 0,w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
return s * w;
}
void YYCH()
{
mu[1] = 1;
for(int i = 2; i <= N-5; i++)
{
if(!check[i])
{
prime[++tot] = i;
mu[i] = -1;
}
for(int j = 1; j <= tot && i * prime[j] <= N-5; j++)
{
check[i * prime[j]] = 1;
if(i % prime[j] == 0)
{
mu[i * prime[j]] = 0;
break;
}
else mu[i * prime[j]] = -mu[i];
}
}
for(int i = 1; i <= tot; i++)
{
for(int j = 1; j * prime[i] <= N-5; j++)
{
ans[j * prime[i]] += mu[j];
}
}
for(int i = 1; i <= N-5; i++) ans[i] = ans[i-1] + ans[i];
}
int calc(int n,int m)
{
int res = 0;
if(n > m) swap(n,m);
for(int l = 1, r; l <= n && l <= m; l = r+1)
{
r = min(n/(n/l),m/(m/l));
res += (ans[r] - ans[l-1]) * (n/l) * (m/l);
}
return res;
}
signed main()
{
T = read(); YYCH();
while(T--)
{
n = read(); m = read();
printf("%lld
",calc(n,m));
}
return 0;
}
其实这道题还可以做到 (O(Tsqrt(n) + n)) 的。
最后一步 (dp) 化 (Q) 的时候，可以变为： (displaystylesum_{Q=1}^{n} {nover Q}{mover Q} sum_{dmid Q} mu(d) isp({Qover d}))
后面那个 (displaystyle F(Q) = sum_{dmid Q} mu(d) isp({Qover d})) 是可以线性筛的。
设 (i = p_1p_2p_3....), 只有当 ({Qover d} = p1,p2,p3...) 时，(isp({Qover d})) 才成立。
1.当 (Q) 为质数的时候,显然 (F(Q) = 1)
2.当 (Q = 1) 时，显然 (F(Q) = 0)
3.当 (i) % (prime[j] == 0) 的时候： (F(i * prime[j]) = mu(i))
证明：
此时 (prime[j]) 为 $i $ 的最小质因子 (p_1) 。
(F (i) = mu({i over p_1}) + mu({iover p_2}) + ....mu({iover p_n}))
(F(i * p_1) = mu({i * p_1 over p_1}) + mu({i * p_1 over p_2}) + ....mu({i * p1over p_n}))
显然 (i * p_1) 分解质因数后， (p_1) 的次数是大于等于 (2) 的，所以除了 (mu({i * p_1over p1} )) 之外，其他都为零。
因为 (p1) 的次数大于等于 2，(mu({i*p1over p_n}) = 0) 。
所以 (F(i * p1) = mu(i)).
4.当 (i) % (prime[j] != 0) 时： (F(i * prime[j]) = mu[i]-F(i))
证明：
此时 (prime[j]) 为 $i $ 的最小质因子 (p_0) 。
(F (i) = mu({i over p_1}) + mu({iover p_2}) + ....mu({iover p_n}))
(F(i * p_0) = mu({i * p_0over p_0}) + mu({i * p_0 over p_1}) + mu({i * p_0 over p_2}) + ....mu({i * p0over p_n}))
显然有 (mu({i*p_0over p_1}) = -mu({iover p_1})) 。假设 ({iover p_1} = x) ,他分解后质因数为 (x = p_1p_2...p_n)
({i*p_0over p_1}) 比 ({iover p_1}) 多了个质因子 (p_0), 所以 (mu({i*p_0over p_1}) = -mu({iover p_1})) 。
综上：
(F(i * p_0) = mu({i * p_0over p_0}) + mu({i * p_0 over p_1}) + mu({i * p_0 over p_2}) + ....mu({i * p0over p_n}))
(= mu(i) -mu({iover p_1}) -mu({iover p_2}) .....-mu({iover p_n}))
(= mu(i) - F(i))
然后就可以直接线性筛了。
Code
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
const int N = 1e7+10;
int T,n,m,tot;
int prime[N],mu[N],ans[N];
bool check[N];
inline int read()
{
int s = 0,w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
return s * w;
}
void YYCH()
{
mu[1] = 1; ans[1] = 0;
for(int i = 2; i <= N-5; i++)
{
if(!check[i])
{
prime[++tot] = i;
mu[i] = -1;
ans[i] = 1;
}
for(int j = 1; j <= tot && i * prime[j] <= N-5; j++)
{
check[i * prime[j]] = 1;
if(i % prime[j] == 0)
{
mu[i * prime[j]] = 0;
ans[i * prime[j]] = mu[i];
break;
}
else
{
mu[i * prime[j]] = -mu[i];
ans[i * prime[j]] = mu[i] - ans[i];
}
}
}
for(int i = 1; i <= N-5; i++) ans[i] = ans[i-1] + ans[i];
}
int calc(int n,int m)
{
int res = 0;
if(n > m) swap(n,m);
for(int l = 1, r; l <= n && l <= m; l = r+1)
{
r = min(n/(n/l),m/(m/l));
res += (ans[r] - ans[l-1]) * (n/l) * (m/l);
}
return res;
}
signed main()
{
T = read(); YYCH();
while(T--)
{
n = read(); m = read();
printf("%lld
",calc(n,m));
}
return 0;
}