题解 P1835 【素数密度_NOI导刊2011提高(04)】

LuckyCloud

2018-05-12 15:18:01

Solution

~~**裸的筛法大家应该都会**~~**但是裸的筛法貌似没法用了怎么办呢?** 其实有个东西叫Miller-Rabbin,貌似是一个基于概率的算法,反正能用~~一些神奇的操作~~判断出当前这个数是不是质数,是不是感觉和普通筛法的某一步有点相似——如果这个数是质数那么就筛去这个数的倍数,但是如果这个数没被筛过还是得用神奇的Miller-Rabbin判断一下。~~关于神奇的Miller-Rabbin请查询百度~~ ```cpp #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int prime[3]={2,7,61}; bool yes[1000003]; long long pow(long long a,long long b,long long mod) { long long cnt=1; a=a%mod; while (b) { if (b&1) cnt=cnt*a % mod; b>>=1; a=a*a%mod; } return cnt; } bool MR(long long x) { long long r,q=0,cnt,tot; if (x<2) return false; for (int i=0;i<3;i++) { if (x==prime[i]) return true; if (x%prime[i]==0) return false; } r=x-1; while (!(r&1)) { r>>=1; q++; } for (int i=0;i<3;i++) { tot=q; cnt=pow(prime[i],r,x); while (tot) { if (cnt*cnt%x==1 && cnt!=1 && cnt!=x-1) return false; cnt=cnt*cnt%x; tot--; } if (cnt%x!=1) return false; } return true; } long long l,r,ans; int main() { memset(yes,true,sizeof(yes)); scanf("%lld%lld",&l,&r); for (long long i=l;i<=r;i++) { if (!yes[i-l+1]) continue; if (MR(i)) { long long j=i+i; while (j<=r) { yes[j-l+1]=false; j=j+i; } ans++; } } printf("%lld\n",ans); return 0; } ```