首页 > 代码库 > [BZOJ2820]YY的GCD
[BZOJ2820]YY的GCD
[BZOJ2820]YY的GCD
试题描述
神犇YY虐完数论后给傻×kAc出了一题给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对kAc这种傻×必然不会了，于是向你来请教……多组输入
输入
第一行一个整数T 表述数据组数接下来T行，每行两个正整数，表示N, M
输出
T行，每行一个整数表示第i组数据的结果
输入示例
2 10 10 100 100
输出示例
30 2791
数据规模及约定
T = 10000
N, M <= 10000000
题解
枚举公约素数 p，那么有
令 T = dp，并交换一下枚举顺序，得到
于是我们只需要预处理出
的前缀和，就可以 O(sqrt(n)) 回答每次询问了。
我们暴力枚举每个质数 p，然后更新 p 的倍数位置上的值，得到 f(T)（复杂度为 O(n / ln(n) * log(n))），然后 O(n) 求前缀和即可。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *Tail;
inline char Getchar() {
if(Head == Tail) {
int l = fread(buffer, 1, BufferSize, stdin);
Tail = (Head = buffer) + l;
}
return *Head++;
}
int read() {
int x = 0, f = 1; char c = Getchar();
while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = Getchar(); }
while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = Getchar(); }
return x * f;
}
#define maxn 10000010
#define LL long long
int prime[maxn], cp, mu[maxn], f[maxn], sf[maxn];
bool vis[maxn];
void init() {
mu[1] = 1;
for(int i = 2; i < maxn; i++) {
if(!vis[i]) prime[++cp] = i, mu[i] = -1;
for(int j = 1; i * prime[j] < maxn && j <= cp; j++) {
vis[i*prime[j]] = 1;
if(i % prime[j] == 0){ mu[i*prime[j]] = 0; break; }
mu[i*prime[j]] = -mu[i];
}
}
for(int i = 1; i <= cp; i++)
for(int j = 1; prime[i] * j < maxn; j++) f[j*prime[i]] += mu[j];
for(int i = 1; i < maxn; i++) sf[i] = sf[i-1] + f[i];
return ;
}
int main() {
init();
int T = read();
while(T--) {
int n = read(), m = read();
if(n > m) swap(n, m);
LL ans = 0;
for(int i = 1, lst; i <= n; i = lst + 1) {
lst = min(n / (n / i), m / (m / i));
ans += (LL)(n / i) * (m / i) * (sf[lst] - sf[i-1]);
}
printf("%lld\n", ans);
}
return 0;
}
[BZOJ2820]YY的GCD
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。