HDU2973

../../算法知识/数论/威尔逊定理

给定 $n$ , 计算

$\sum_{k = 1}^{n} ⌊ \frac{(3 k + 6)! + 1}{3 k + 7} - ⌊ \frac{(3 k + 6)!}{3 k + 7} ⌋ ⌋$

思路：
容易想到威尔逊定理

若 $3 k + 7$ 是质数，则
$(3 k + 6)! \equiv - 1 (\mod 3 k + 7)$

易得 $(3 k + 6)! + 1 = m (3 k + 7)$

则
$⌊ \frac{(3 k + 6)! + 1}{3 k + 7} - ⌊ \frac{(3 k + 6)!}{3 k + 7} ⌋ ⌋ = ⌊ m - ⌊ m - \frac{1}{3 k + 7} ⌋ ⌋ = 1$

若 $3 k + 7$ 不是质数 ,则有 $(3 k + 7) ∣ (3 k + 6)!$ (由威尔逊定理的推论）

设 $(3 k + 6)! = k (3 k + 7)$ ，

$⌊ \frac{(3 k + 6)! + 1}{3 k + 7} - ⌊ \frac{(3 k + 6)!}{3 k + 7} ⌋ ⌋ = ⌊ k + \frac{1}{3 k + 7} - k ⌋ = 0$

因此

$\sum_{k = 1}^{n} ⌊ \frac{(3 k + 6)! + 1}{3 k + 7} - ⌊ \frac{(3 k + 6)!}{3 k + 7} ⌋ ⌋ = \sum_{k = 1}^{n} [3 k + 7 is prime]$

考虑筛法: ../../算法知识/数论/素数筛法

#include <iostream>

const int M = 1e6 + 5, N = 3 * M + 7;

bool not_prime[N];
int sum[M];

int main() {
  for (int i = 2; i < N; ++i)
    if (!not_prime[i])
      for (int j = 2; j * i < N; ++j) 
      not_prime[j * i] = 1;
  for (int i = 1; i < M; ++i) 
  sum[i] = sum[i - 1] + !not_prime[3 * i + 7];

  int t;
  std::cin >> t;
  while (t--) {
    int n;
    std::cin >> n;
    std::cout << sum[n] << std::endl;
  }
}