版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
title: "题解 - [HDU 2973] YAPTCHA" categories:
给定 $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}^+] $$