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

2018-05-12 15:18:01


裸的筛法大家应该都会但是裸的筛法貌似没法用了怎么办呢? 其实有个东西叫Miller-Rabbin,貌似是一个基于概率的算法,反正能用一些神奇的操作判断出当前这个数是不是质数,是不是感觉和普通筛法的某一步有点相似——如果这个数是质数那么就筛去这个数的倍数,但是如果这个数没被筛过还是得用神奇的Miller-Rabbin判断一下。关于神奇的Miller-Rabbin请查询百度

#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;
}