题目描述
求一个给定的圆(x^2+y^2=r^2)，在圆周上有多少个点的坐标是整数。
输入输出格式
输入格式：
r
输出格式：
整点个数
输入输出样例
输入样例#1：
4
输出样例#1：
4
说明
n<=2000 000 000
/*
处理筛法：
筛素数筛到r<=2e9的话显然数组开不下
显然一个数有<=1个大于它的sqrt的素因子
所以我们筛小于等于sqrt(r)的范围内的素数
然后用筛出来的素数将n质因数分解后可能r!=1
这个时候的n就是n的那个大于sqrt(r)的素因子 处理计算：
如果prime[i]%4==3的话，prime[i]就是个素数，同时也是个高斯素数，对答案无影响
如果prime[i]%4==1，就记录prime[i]的指数tmp，让ans*=(tmp*2+1)
至于为什么这么做，自己看视频去。
https://www.bilibili.com/video/av12131743/
*/ #include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std; const int N=4e4+; bool flag[N];
int prime[N],cnt;
inline void init()
{
for(int i=;i<N;++i)
{
if(!flag[i])
prime[++cnt]=i;
for(int j=,k;j<=cnt&&(k=prime[j]*i)<N;++j)
{
flag[k]=;
if(i%prime[j]==)
break;
}
}
} int n;
int main()
{
init();
scanf("%d",&n);
while((n&)^)
n>>=;
int ans=;
for(int i=,tmp=;i<=cnt&&n!=;++i)
{
if(n%prime[i])
continue;
tmp=;
while(n%prime[i]==)
++tmp,n/=prime[i];
if(prime[i]%==)
ans*=(tmp<<|);
}
if(n>&&n%==)
ans*=;
cout<<(ans<<);
return ;
}
/*
处理筛法：
筛素数筛到r<=2e9的话显然数组开不下
显然一个数有<=1个大于它的sqrt的素因子
所以我们筛小于等于sqrt(r)的范围内的素数
然后用筛出来的素数将n质因数分解后可能r!=1
这个时候的n就是n的那个大于sqrt(r)的素因子 处理计算：
如果prime[i]%4==3的话，prime[i]就是个素数，同时也是个高斯素数，对答案无影响
如果prime[i]%4==1，就记录prime[i]的指数tmp，让ans*=(tmp*2+1)
至于为什么这么做，自己看视频去。
https://www.bilibili.com/video/av12131743/
*/ #include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std; const int N=4e4+; bool flag[N];
int prime[N],cnt;
inline void init()
{
for(int i=;i<N;++i)
{
if(!flag[i])
prime[++cnt]=i;
for(int j=,k;j<=cnt&&(k=prime[j]*i)<N;++j)
{
flag[k]=;
if(i%prime[j]==)
break;
}
}
} int n;
int main()
{
init();
scanf("%d",&n);
while((n&)^)
n>>=;
int ans=;
for(int i=,tmp=;i<=cnt&&n!=;++i)
{
if(n%prime[i])
continue;
tmp=;
while(n%prime[i]==)
++tmp,n/=prime[i];
if(prime[i]%==)
ans*=(tmp<<|);
}
if(n>&&n%==)
ans*=;
cout<<(ans<<);
return ;
}