題目鏈接
題意:求出題目中那個公式的答案
思路:
當3?k+7非素數的時候,那麼(3?k+6)!(因為必然能找到兩個因子相乘)
所以原式為0
當3?k+7為素數的時候,根據威爾遜定理,((3?k+6)!+1)%(3?k+7)==0,因此原式可以轉化為[x - (x - 1)] = 1
因此問題轉化為只要判斷3 * k + 7是不是素數,那麼就很好辦了,預處理出素數表,再預處理出答案即可
代碼:
#include#include const long long N = 1000005; bool ispri[N * 3]; int ans[N], t, n; int main() { for (long long i = 2; i < N * 3; i++) { if (ispri[i]) continue; for (long long j = i * i; j < N * 3; j += i) ispri[j] = true; } for (int i = 2; i < N; i++) ans[i] = ans[i - 1] + (!ispri[3 * i + 7]); scanf("%d", &t); while (t--) { scanf("%d", &n); printf("%d\n", ans[n]); } return 0; }