题解 - [HDU 2973] YAPTCHA

发表于 更新于 分类于 ， 本文字数： 216 阅读时长 ≈ 1 分钟

题目链接

题意简述

给定 \(n\), 计算

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

解题思路

  • 若 \(3k+7\) 是质数，则由 Wilson 定理可知

    \[ (3k+6)!\equiv-1\pmod{3k+7} \]

    设 \((3k+6)!+1=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-\left\lfloor k-\frac{1}{3k+7}\right\rfloor\right\rfloor=1 \]

  • 若 \(3k+7\) 不是质数，则有 \((3k+7)\mid(3k+6)!\), 即

    \[ (3k+6)!\equiv 0\pmod{3k+7} \]

    设 \((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\in\text{Prime}^+] \]

代码

Show code

HDU_2973view raw
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
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <iostream>
using namespace std;
const int M = 1e6 + 5, N = 3 * M + 7;
bool vis[N];
int sum[M];
int main() {
  for (int i = 2; i < N; ++i)
    if (!vis[i])
      for (int j = 2; j * i < N; ++j) vis[j * i] = 1;
  for (int i = 1; i < M; ++i) sum[i] = sum[i - 1] + !vis[3 * i + 7];
  int kase;
  cin >> kase;
  while (kase--) {
    int n;
    cin >> n;
    cout << sum[n] << endl;
  }
}