吃雪糕的意外收获 —— CF113C Double Happiness 题解

longyitongxue · 2026-07-23 11:07:03 · 题解

::::info[HaoBa 发雪糕提到] 昨天下午吃过雪糕的现在也可以吃，就如 CF 有道题叫《双倍幸福》（Double Happiness）。 :::: 点开来看，发现可以写题解？！！！纪念一下。

神秘数论。这题是个费马二平方定理：除 2 以外的所有的质数都可以分为两类：4x+1 和 4x+3。而我们的 4x+1 又可以写成两个平方数的和。我们用线性筛筛出 [2,r] 的质数（注意 1\le r\le3\times10^8 因此埃氏筛会被卡），然后去看哪些 >l 且 \bmod 4=1（即这个数可以表示为 4x+1 且在 [l,r] 范围内），统计个数即可。注意，2=1+1=1^2+1^2，因此要特判 2 的情况。

::::success[Code]

需要使用 bitset 来存储 is_Prime 而不是 bool 因为 bitset 的空间是 bool 的 \dfrac{1}{8}，使用 bool 会 MLE；需控制好 ans 数组的大小防止 MLE。

#include<bits/stdc++.h>
#define int int_fast32_t
using namespace std;
bitset<int(3e8+5)> is_Prime;
int ans[int(2e7+5)],cnt;
int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int l,r;
    cin>>l>>r;
    is_Prime[1]=1;
    for(int i=2;i<=r;i++){
        if(!is_Prime[i]){
            ans[++cnt]=i;
        }
        for(int j=1;j<=cnt&&i*ans[j]<=r;j++){
            is_Prime[i*ans[j]]=1;
            if(!(i%ans[j]))break;
        }
    }
    int tot=0;
    for(int i=1;i<=cnt;i++){
        if(ans[i]>=l&&ans[i]%4==1){
            tot++;
        }
    }
    if(l<=2&&r>=2)tot++;
    cout<<tot;
    return 0;
}

::::