UVa 11440 Help Tomisu (欧拉函数)

发表于 更新于 分类于

题目

题目大意

给定正整数\(N\)和\(M\), 统计\(2\)和\(N!\)之间有多少个整数\(x\)满足: \(x\)的所有素因子都大于\(M\)(\(2 ≤ N ≤ 10^7\), \(1 ≤ M ≤ N\), \(N - M ≤ 10^5\))。输出答案除以\(100000007\)的余数。例如, \(N = 100\), \(M = 10\)时的答案为\(43274465\)。

题解

因为\(M ≤ N\), 所以\(N!\)是\(M!\)的整数倍。所有素因子都大于\(M\)等价于和\(M!\)互质。根据最大公约数的性质, 对于\(k > M!\), \(k\)与\(M!\)互质当且仅当\(k\ mod\ M!\)与\(M!\)互质。这样就只需要求出不超过\(M!\)且与\(M!\)互质的正整数个数, 再乘以\(\frac{N!}{M!}\)即可。

根据欧拉函数的公式:

\[\phi(n) = n(1 - \frac{1}{p_1})(1 - \frac{1}{p_2})\cdots(1 - \frac{1}{p_k})\]

如果\(n\)不是质数, 那么\(n!\)与\((n - 1)!\)的质因子集合相同, 因此\(phifac(n) = n\ phifac(n - 1)\); 如果\(n\)是质数, 那么还会多一项\((1 - \frac{1}{n})\), 即\(phifac(n) = (n - 1)\ phifac(n - 1)\)。

代码

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
#include <cstdio>
#include <cstring>
const long long kMod(100000007);
long long phifac[10000010] = {0, 1, 1};
bool mark[10000010];
long long n, m;
long long ans;
int main(int argc, char const *argv[]) {
  memset(mark, true, sizeof(mark));
  mark[0] = mark[1] = false;
  for (register int i(2); i <= 10000000; ++i) {
    if (mark[i]) {
      for (register int j(2); i * j <= 10000000; ++j) {
        mark[i * j] = false;
      }
    }
  }
  for (register long long i(3); i <= 10000000; ++i) {
    phifac[i] = phifac[i - 1] * (mark[i] ? i - 1 : i) % kMod;
  }
  while (~scanf("%lld %lld", &n, &m) && (n || m)) {
    ans = phifac[m];
    for (register long long i(m + 1); i <= n; ++i) ans = ans * i % kMod;
    printf("%lld\n", (ans - 1 + kMod) % kMod);
  }
  return 0;
}