BZOJ3798 特殊的质数

2014.12.12 13:09 Fri| 2 visits oi_2015| 2015_刷题日常| Text

又一道分块打表水题!

Solution

费马平方和定理(Fermat's theorem on sums of two squares):

In additive number theory, Pierre de Fermat's theorem on sums of two squares states that an odd prime p is expressible as

with x and y integers, if and only if

奇素数能表示为两个平方数之和的充分必要条件是该素数被4除余1。

这样我们就可以用分块打表的方式AC此题了!

bitset压缩空间,先线性筛出 $3\times10^8$ 以内的所有素数,然后,,,这叫一个爽啊!

Code

打表器

#include <bits/stdc++.h>
using namespace std;
#define block 100000

bitset<300000005> flag;
int p[17000005],sqr[17325],tot,ans=1;

void getprime(int x)
{
    for(int i=2;i<=x;i++)
    {
        if(flag[i]==0) p[++tot]=i;
        for(int j=1;i*p[j]<=x;j++)
        {
            flag[i*p[j]]=1;
            if(i%p[j]==0) break;
        }
    }
}

int main()
{
    getprime(300000000);
    for(int i=2;i<=tot;i++)
    {
        if(p[i]/block!=p[i-1]/block) cout<<ans<<',';
        if(p[i]%4==1) ans++;
    }
    cout<<ans<<endl;
    return 0;
}

程序

#include <bits/stdc++.h>
using namespace std;
#define block 100000

int sqr[17325],tot,a,b;
int cheat[]={0,4784,8978,12981,……,8115467,8118011,8120631,8123161,8125719};

void getsqr()
{
    for(int i=1;i<=17321;i++)
        sqr[i]=i*i;
}

inline bool check(int x)
{
    if(x==2) return true;
    if(x%4!=1) return false;
    for(int i=2;i*i<=x;i++)
        if(x%i==0) return false;
    for(int j=1,q;(q=sqr[j])<x;j++)
        if(sqr[(int)sqrt(1e-4+x-q)]+q==x)
            return true;
    return false;
}

int count(int x)
{
    int re=cheat[x/block];
    for(int i=x/block*block+1;i<=x;i++)
        if(check(i)) re++;
    return re;
}

int main()
{
    cin>>a>>b;
    getsqr();
    cout<<count(b)-count(a-1)<<endl;
    return 0;
}