求 ∑ gcd(x, y) = p ( p 是质数, 1 <= x <= n, 1 <= m <= m)
这个编辑器写不了数学公式...推推就可以了...然后就是分块
复杂度...素数个数大概是n/logn, 一个数找倍数的均摊复杂度O(logn)(Orz Cyan), 所以就是O(n)预处理, 询问O(sqrt(n))
------------------------------------------------------------------
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 10000009;
bool check[maxn];
int prime[maxn], N = 0, mu[maxn], f[maxn];
void init() {
memset(check, false, sizeof check);
memset(f, 0, sizeof f);
mu[1] = 1;
for(int i = 2; i < maxn; i++) {
if(!check[i]) {
prime[N++] = i;
mu[i] = -1;
}
for(int j = 0; j < N && prime[j] * i < maxn; j++) {
check[i * prime[j]] = true;
if(i % prime[j])
mu[i * prime[j]] = -mu[i];
else {
mu[i * prime[j]] = 0;
break;
}
}
}
for(int i = 0; i < N; i++)
for(int j = 0; j * prime[i] < maxn; j++)
f[j * prime[i]] += mu[j];
for(int i = 1; i < maxn; i++)
f[i] += f[i - 1];
}
int main() {
init();
int t;
scanf("%d", &t);
while(t--) {
int n, m;
ll ans = 0;
scanf("%d%d", &n, &m);
if(n > m) swap(n, m);
for(int L = 1; L <= n; L++) {
int R = min(n / (n / L), m / (m / L));
ans += 1LL * (f[R] - f[L - 1]) * (n / L) * (m / L);
L = R;
}
printf("%lld
", ans);
}
return 0;
}
------------------------------------------------------------------
2820: YY的GCD
Time Limit: 10 Sec Memory Limit: 512 MBSubmit: 989 Solved: 497
[Submit][Status][Discuss]
Description
神犇YY虐完数论后给傻×kAc出了一题
给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对
kAc这种傻×必然不会了，于是向你来请教……
多组输入
Input
第一行一个整数T 表述数据组数
接下来T行，每行两个正整数，表示N, M
Output
T行，每行一个整数表示第i组数据的结果
Sample Input
2
10 10
100 100
10 10
100 100
Sample Output
30
2791
2791
HINT
T = 10000
N, M <= 10000000