BZOJ 2818 GCD(欧拉函数)

题目链接:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=37161

题意:gcd(x, y) = 质数, 1 <= x, y <= n的对数

思路:显然gcd(x, y) = k, 1 <= x, y <= n的对数等于求(x, y) = 1, 1 <= x, y <= n/k的对数。所以,枚举每个质数p,然后求gcd(x, y) = 1, 1 <= x, y <= n/p的个数。那么问题的关键就是怎么求gcd(x, y) = 1, 1 <= x, y <= n / pi,在[1, y]y互质的数有phi(y)个,如果我们令x < y,那么答案就是sigma(phi(y))。因为x, y是等价的,所以答案*2,又因为(1, 1)只有一对,所以-1。最终答案为sigma(sigma(phi(n/prime[i])) * 2 - 1)

code:

 #include <cstdio>
#include <cstring>
typedef long long LL;
const int MAXN = ; LL phi[MAXN];
int primes[MAXN];
bool is[MAXN];
int cnt; void init(int n)
{
phi[] = 1L;
cnt = ;
memset(is, false, sizeof(is));
for (int i = ; i <= n; ++i) {
if (!is[i]) {
primes[cnt++] = i;
phi[i] = i - ;
}
for (int j = ; j < cnt && i * primes[j] <= n; ++j) {
is[i * primes[j]] = true;
if (i % primes[j] == ) phi[i * primes[j]] = phi[i] * primes[j];
else phi[i * primes[j]] = phi[i] * (primes[j] - );
}
}
} int main()
{
int n;
while (scanf("%d", &n) != EOF) {
init(n);
LL ans = ;
for (int i = ; i <= n; ++i) phi[i] += phi[i - ];
for (int i = ; i < cnt; ++i) {
ans += phi[n / primes[i]] * - ;
}
printf("%lld\n", ans);
}
return ;
}
上一篇:linux:安装ubuntu18-04


下一篇:Java高阶语法---Volatile