Sol.CF113C

前置知识:

费马二平方和定理

内容如下：

1. 除 \(2\) 以外的素数 \(x\) 都可以表示成 \(x\equiv 1 \pmod{4}\) 或 \(x\equiv 3 \pmod{4}\)。
2. 当且仅当素数 \(x\) 可以表示成 \(x\equiv 1 \pmod{4}\) 时， \(x\) 为两数平方之和。

为了更高效，筛素数时使用欧拉筛，注意到 int 会爆，所以用 bitset。

欧拉筛部分代码如下

for(int i=2;i<=x;i++){
	if(!vis[i])isp[++sum]=i;
	for(int j=1;j<=sum&&i*isp[j]<=x;j++){
		vis[isp[j]*i]=1;
		if(i%isp[j]==0)break;
	}
}

最后累计答案并输出，注意要特判!

for(register int i=1;i<=sum;i++)
    if (isp[i]%4==1&&isp[i]>=l)
		ans++;
if(l<=2&&r>=2)ans++;