[HDOJ3501] Calculation 2 (容斥 or 欧拉函数)

链接:http://acm.hdu.edu.cn/showproblem.php?pid=3501

求一个数n的所有小于它并且与它不互质的数的和。

打算复习一波欧拉函数的,结果这题发现可以容斥。

我们知道如果一个数$n$含有因数$x$,那么$x$的倍数都和$n$不互质,且质因数至少为$x$。

我们可以知道,对于任意小于$n$的因数$x$,对本题的贡献为$x+2x+3x+…+kx=\frac{k(k+1)}{2}x$,其中$k$为$n$对$x$的倍数。

于是直接对$n$分解因数,再容斥。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const LL mod = 1e9+7;
LL n;

LL exgcd(LL a, LL b, LL &x, LL &y) {
if(b == 0) {
x = 1;
y = 0;
return a;
}
else {
LL ret = exgcd(b, a%b, x, y);
LL tmp = x;
x = y;
y = tmp - a / b * y;
return ret;
}
}
LL inv(LL a) {
LL x, y;
exgcd(a, mod, x, y);
return (x % mod + mod) % mod;
}

signed main() {
// freopen("in", "r" ,stdin);
while(~scanf("%lld",&n) && n) {
LL t = n;
vector<LL> p;
for(LL i = 2; i * i <= n; i++) {
if(n % i == 0) p.push_back(i);
while(n % i == 0) n /= i;
}
if(n > 1) p.push_back(n);
int nn = 1 << p.size();
LL ret = 0;
for(int i = 1; i < nn; i++) {
LL tmp = 1;
for(int j = 0; j < p.size(); j++) {
if(i & (1 << j)) {
tmp *= p[j];
}
}
LL cnt = t / tmp;
tmp = cnt * (cnt - 1) % mod * inv(2) % mod * tmp % mod;

if(__builtin_popcount(i) & 1) {
ret += tmp; ret %= mod;
}
else {
ret -= tmp; ret += mod; ret %= mod;
}
}
printf("%lld\n", ret);
}
return 0;
}

再来考虑欧拉函数,知道一个定理:小于$n$的数,且与$n$互质的数的和为:
$$
\frac{\phi(n)×n}{2}
$$
然而小于$n$的数的和为$\frac{n(n-1)}{2}$,于是我们一减:
$$
\frac{n(n-1-\phi(n))}{2}
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
signed main() {
// freopen("in", "r" ,stdin);
while(~scanf("%lld",&n) && n) {
LL ret = n, t = n;
for(LL i = 2; i * i <= n; i++) {
if(n % i == 0) ret = ret / i * (i-1);
while(n % i == 0) n /= i;
}
if(n > 1) ret = ret / n * (n-1);
LL p = t * (t - 1 - ret) / 2;
cout << p % mod << endl;
}
return 0;
}