HDU2973

[[../../ACM/数论/威尔逊定理]]

给定 \(n\), 计算

\(\sum_{k=1}^n\left\lfloor\frac{(3k+6)!+1}{3k+7}-\left\lfloor\frac{(3k+6)!}{3k+7}\right\rfloor\right\rfloor\)

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

1. 若 \(3k+7\) 是质数，则 \((3k+6)!\equiv-1\pmod{3k+7}\)

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

则 \(\left\lfloor\frac{(3 k+6)!+1}{3 k+7}-\left\lfloor\frac{(3 k+6)!}{3 k+7}\right\rfloor\right\rfloor=\left\lfloor m-\left\lfloor m-\frac{1}{3 k+7}\right\rfloor\right\rfloor=1\)

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

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

\(\left\lfloor\frac{(3k+6)!+1}{3k+7}-\left\lfloor\frac{(3k+6)!}{3k+7}\right\rfloor\right\rfloor=\left\lfloor k+\frac{1}{3k+7}-k\right\rfloor=0\)

因此

\(\sum_{k=1}^n\left\lfloor\frac{(3k+6)!+1}{3k+7}-\left\lfloor\frac{(3k+6)!}{3k+7}\right\rfloor\right\rfloor=\sum_{k=1}^n[3k+7\text{ is prime}]\)

考虑筛法: [[../../ACM/数论/素数筛法]]

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