前置知识:
费马二平方和定理
内容如下：
- 除 \(2\) 以外的素数 \(x\) 都可以表示成 \(x\equiv 1 \pmod{4}\) 或 \(x\equiv 3 \pmod{4}\)。
- 当且仅当素数 \(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++;