YY的GCD
友情链接:
神犇YY虐完数论后给傻×kAc出了一题
给定$N$, $M$,求 $1le xle N$, $1le yle M$ 且 $gcd(x, y)$ 为质数的 $(x, y)$ 有多少对
kAc这种傻×必然不会了,于是向你来请教……
多组输入
Input
第一行一个整数 $T$ 表述数据组数
接下来 $T$ 行,每行两个正整数,表示 $N$, $M$
Output
T行,每行一个整数表示第i组数据的结果
Sample Input
210 10100 100
Sample Output
302791
Hint
$T = 10000$
$N, Mle 10000000$
题意
给定 $N, M$,求 $sum_{i=1}^{N}sum_{j=1}^{M}isprime(gcd(i, j))$ 的值,即 $[1, M]$ 和 $[1, N]$ 两个区间中各取一个数,形成一个数对,且 $gcd(i,j)$ 为质数,问这样的数对有多少个。
解决方案
考虑枚举质数 $d$ ,则原式为:
后面两个 $sum$ 为:
$therefore $ 原式为:
令 $T = kd$ ,则有:
到这里来式子就比较明了了,$lfloordfrac{N}{T}rfloorlfloordfrac{M}{T}rfloor$ 是很明显的分块,可以办到 $O(sqrt{n})$ 的复杂度,后面那一部分如何处理?
可以考虑枚举质数进行打表,$n$ 范围内的质数有 $dfrac{n}{ln n}$ 个,而用每一个质数去筛,均摊到每一个质数的复杂度为 $O(ln n)$ ,所以线性筛出所有质数,然后用这些质数再去筛的复杂度为 $O(n)$ ,总的时间复杂度为 $O(sqrt{n})$
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e7 + 10;
bool vis[maxn];
int prime[maxn];
int mu[maxn];
ll f[maxn];
int tot;
void eular() {
vis[0] = vis[1] = true;
mu[1] = 1;
for (int i = 2; i < maxn; i++) {
if (!vis[i]) {
prime[tot++] = i;
mu[i] = -1;
}
for (int j = 0; j < tot && i * prime[j] < maxn; j++) {
vis[i * prime[j]] = true;
mu[i * prime[j]] = -mu[i];
if (i % prime[j] == 0) {
mu[i * prime[j]] = 0;
break;
}
}
}
}
void init() {
for (int i = 0; i < tot; i++) {
for (int j = prime[i]; j < maxn; j += prime[i]) {
f[j] += mu[j / prime[i]];
}
}
for (int i = 1; i < maxn; i++) {
f[i] += f[i - 1];
}
}
int main() {
eular();
init();
int T;
scanf("%d", &T);
while (T--) {
int n, m;
scanf("%d%d", &n, &m);
int tmp = min(n, m);
ll ans = 0;
for (int l = 1, r; l <= tmp; l = r + 1) {
r = min(n / (n / l), m / (m / l));
ans += (f[r] - f[l - 1]) * (n / l) * (m / l);
}
printf("%lldn", ans);
}
return 0;
}
刚刚开始写这种题还是要好好的把公式推一遍的。
近期评论