【题意】给定 N, M, 求 1<=x<=N, 1<=y<=M 且 gcd(x, y) 为质数的 (x, y) 有多少对. T<=10^4,N,M<=10^7.
【算法】数论 (莫比乌斯反演)
【题解】公式推导见 DQSSS .
推到 ans= Σp 是素数 Σd≤mins μ(d) * (n/pd) * (m/pd),mins=min(n/p,m/p).
使用 枚举取值的方法 再枚举素数单次询问复杂度√n*(n/ln n), 显然不能满足要求.
问题在于枚举素数, 令 T=pd, 则:
ans= ΣT≤mins (n/T) * (m/T)*Σp|T&&p 是素数 μ(T/p),mins=min(n,m).
后面部分可以枚举素数的倍数预处理出μ前缀和, 复杂度 O((n/ln n)*ln n) 即 O(n).
每次询问再枚举取值 O(√n) 解决.
总复杂度 O(T*√n+n).
#include < cstdio > #include < cstring > #include < algorithm > #define ll long long using namespace std;
const int maxn = 10000010,
N = 10000000;
int miu[maxn],
mius[maxn],
prime[maxn],
tot;
ll s[maxn];
bool mark[maxn];
void pre() {
miu[1] = 1;
for (int i = 2; i <= N; i++) {
if (!mark[i]) miu[prime[++tot] = i] = -1;
for (int j = 1; j <= tot && i * prime[j] <= N; j++) {
mark[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
miu[i * prime[j]] = -miu[i];
}
}
for (int i = 1; i <= tot; i++) {
for (int j = prime[i]; j <= N; j += prime[i]) mius[j] += miu[j / prime[i]];
}
for (int i = 1; i <= N; i++) s[i] = s[i - 1] + mius[i];
}
int main() {
pre();
int T,
n,
m;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
int pos = 0,
mins = min(n, m);
ll ans = 0;
for (int i = 1; i <= mins; i = pos + 1) {
pos = min(n / (n / i), m / (m / i));
ans += (s[pos] - s[i - 1]) * (n / i) * (m / i);
}
printf("%lld\n", ans);
}
return 0;
}
View Code
来源: http://www.bubuko.com/infodetail-2458279.html