題目：給定一個正整數(shù)n，求表達式 :??的值.
分析：分兩種情況討論。
? ? ? 0.? ?3k+7為素數(shù)時，那么由威爾遜定理知道?,即
? ? ?此時有，，所以?
? ? ? 1.? ?3k+7為合數(shù)時，那么3k+7可以寫成：?那么很明顯a和b在(3k+6)!中都會出現(xiàn)
所以，此時：
所以，綜上，問題就是小于等于n的數(shù)i中，存在多少個i，使得3i+7是素數(shù)。
轉(zhuǎn)：https://blog.csdn.net/acdreamers/article/details/12711223
?在說明一下： 3k+7為素數(shù)的時候 原式=[ m-[m-1] ] ?(少一個倍數(shù)，這時候分母不可拆,還有就是為合數(shù)的時候 ? 可以拆分母,得出為 0
引申無關性質(zhì)：[m-1]=[m]-1

?

#include <bits/stdc++.h> using namespace std; typedef long long ll; #define X 10005 #define inf 0x3f3f3f3f #define one 0x01 #define PI 3.141592653589793238462643383 const int N=5*1e6+5; int mod=2009; int a[N]={0},f[N]={0}; void P() {for(int i=2;i<sqrt(N);++i){if(!a[i]){for(int j=i*i;j<N;j+=i)a[j]=1;}} } void init() {f[1]=0;for(int k=2;k<=1e6;++k) ///k不能到N{if(!a[3*k+7])//注意數(shù)組a[]太小會溢出f[k]=f[k-1]+1;elsef[k]=f[k-1];} } int main() {ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);int n,t;P();init();cin>>t;while(t--){cin>>n;cout<<f[n]<<endl;}return 0; }

?

總結

以上是生活随笔為你收集整理的hdu2973 YAPTCHA的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。