codeforces 113C C. Double Happiness(费马平方和定理+bitset<>)

• 题意：给定区间[L,R],L,R<=3*1e8，问区间中有几个数即能被a^2+b^2表示（a，b是任意整数）,又是素数。
• 题解：
  • 范围太大，可以用bitset打素数表
    • https://blog.csdn.net/zy2317878/article/details/80082863 bitset的用法
  • 费马平方和定理：费马平方和定理的表述是：奇素数能表示为两个平方数之和的充分必要条件是该素数被4除余1。
    • https://zh.wikipedia.org/wiki/%E8%B4%B9%E9%A9%AC%E5%B9%B3%E6%96%B9%E5%92%8C%E5%AE%9A%E7%90%86 费马平方和定理
  • 就酱

#include <cmath>
#include <string>
#include <bitset>
#include <cstdio>
#include <fstream>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 1e8+1e8+1e8;
bitset<maxn> p;

int
main(void) {
      int L, R;
      scanf("%d %d\n", &L, &R);
    p.set();
    for (int i = 3; i*i <= R; i+=2) if (p[i]) for (int j = i*i; j <= R; j+=2*i) p[j] = false;
    int ans = 0;
    for (int i = 5; i <= R; i+=4) if (p[i] && i >= L) ans++;
    ans += (L <= 2 && R >= 2) ? 1 : 0;
    printf("%d\n", ans);

    return 0;
}