题解归档 - cf113C

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf113C
• 本地来源：problems/cf113C/idea.md
• 题目链接：https://codeforces.com/contest/113/problem/C
• 原始标题：CF113C — Double Happiness

思路

CF113C — Double Happiness

题意

区间 ([l,r]) 内，统计同时满足：

• Peter：(i) 为质数；
• Bob：(i=a^2+b^2)（(a,b) 为正整数）

的天数个数。(1\le l\le r\le 3\cdot 10^8)。

关键观察（费马平方和定理）

正整数 (n) 可写成两平方和，当且仅当其质因子分解中，所有 (4k+3) 型素数的指数均为偶数。

因此对素数 (p)：

• (p=2)：(2=1^2+1^2)，合法；
• (p\equiv 1\pmod 4)：作为唯一质因子，指数 1 为偶数… 实际上单素数 (p\equiv1\pmod4) 可写（如 (5=1^2+2^2)）；
• (p\equiv 3\pmod 4)：指数为奇，不可写（如 (3,7,11,\ldots)）。

故答案 = ([l,r]) 中满足 (p=2) 或 (p\equiv 1\pmod 4) 的质数个数。

算法

1. 欧拉筛预处理 (\le \sqrt{r}\approx 17321) 的小素数；
2. 分段筛（块长 (10^6)）标记 ([l,r]) 合数；
3. 扫剩余素数，按模 4 计数。

复杂度：(O\big((r-l)\log\log\sqrt r + \sqrt r\log\log\sqrt r\big))，空间 (O(\sqrt r + \text{块长}))。

样例

• ([3,5])：素数 (3,5)；仅 (5\equiv1\pmod4) → 1。
• ([6,66])：合法素数 (13,17,29,37,41,53,61) → 7。

实现注意

• (l=1) 时跳过 1（非素数）；
• (r-l) 可达 (3\cdot10^8)，必须分段，不可一次开满数组。

代码

来源：problems/cf113C/solution.cpp

/* Author: likely
 * Time: 2026-06-08 05:13:48
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=2e4;
const ll maxn2=1e6;
bool not_prime[maxn+5];
ll prime[maxn+5],tot=0;
bool iscccc[maxn2+5];
void euler_sieve(ll n){
    ll i,j;
    for(i=2;i<=n;i++){
        if(not_prime[i]==0) prime[++tot]=i;
        for(j=1;j<=totandi*prime[j]<=n;j++){
            not_prime[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
}
ll count_seg(ll l,ll r){
    ll i,j,k,ks,ans=0;
    for(i=1;i<=r-l+1;i++) iscccc[i]=0;
    for(i=1;i<=tot;i++){
        if(prime[i]*prime[i]>r) break;
        ks=(l/prime[i]+bool(l%prime[i]))*prime[i];
        for(j=max(ks,prime[i]*2);j<=r;j+=prime[i]) iscccc[j-l+1]=1;
    }
    for(i=max(2ll,l);i<=r;i++){
        if(iscccc[i-l+1]==0 and (i==2 or i%4==1)) ans++;
    }
    return ans;
}
int main(){
    ll l,r,i,j,k,ans;
    cin>>l>>r;
    euler_sieve(maxn);
    ans=0;
    for(i=l;i<=r;i+=maxn2){
        j=min(r,i+maxn2-1);
        ans+=count_seg(i,j);
    }
    cout<<ans<<"\n";
    return 0;
}