[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;
}