[CF113C] Double_Happiness 题解报告

くろねこ · 2018-11-03 21:45:05 · 题解

首先了解一个定理

费马二平方定理

1. 除2以外的所有的素数都可以分为两类:4k + 1,4k + 3
2. 4k + 1可以表示为2个整数的平方和,但4k + 3不行

然后就可以愉快的开始筛素数啦~

由于数据量过大int存不下,故采用bitset(按位存储,空间优秀)

#include <bitset>
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define rg register
int tot,pri[23333333],ans;
bitset <300005005> flag;//我觉得bitset是个好东西 
void make_prime_list(int r)
{
    for (rg int i = 2;i <= r;++i)
    {
        if (!flag[i]) pri[++tot] = i;
        for (rg int j = 1;j <= tot && pri[j] * i <= r;++j)
        {
            flag[i * pri[j]] = true;
            if (i % pri[j] == 0) break;
        }
    }
}
int l,r;
int main()
{
    scanf("%d%d",&l,&r);
    make_prime_list(r);
    for (rg int i = 1;i <= tot;++i)
    {
        //费马二平方定理: 除2以外的所有的素数都可以分为两类:4k + 1,4k + 3
        //4k + 1可以表示为2个整数的平方he,但4k + 3不行 
        if (pri[i] < l) continue;
        if (pri[i] % 4 == 1) ++ans;
    }
    if (l <= 2 && r >= 2) ++ans;
    printf("%d",ans);
}