hdu2973 YAPTCHA

题目：给定一个正整数n，求表达式 :  的值.
分析：分两种情况讨论。
      0.   3k+7为素数时，那么由威尔逊定理知道 ,即
     此时有，，所以 
      1.   3k+7为合数时，那么3k+7可以写成： 那么很明显a和b在(3k+6)!中都会出现
所以，此时：
所以，综上，问题就是小于等于n的数i中，存在多少个i，使得3i+7是素数。
转：https://blog.csdn.net/acdreamers/article/details/12711223
 在说明一下： 3k+7为素数的时候 原式=[ m-[m-1] ]  (少一个倍数，这时候分母不可拆,还有就是为合数的时候   可以拆分母,得出为 0
引申无关性质：[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])//注意数组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的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。