BZOJ 1041 [HAOI2008] 圆上的整点 题解与分析 - 初学者 - 博客频道 - CSDN.NET
【分析】：
样例图示：
首先,最暴力的算法显而易见：枚举x轴上的每个点，带入圆的方程，检查是否算出的值是否为整点，这样的枚举量为2*N，显然过不了全点。
然后想数学方法。
有了上面的推理，那么实现的方法为：
枚举d∈[1,sqrt(2R)]，然后根据上述推理可知：必先判d是否为2R的一约数。
此时d为2R的约数有两种情况：d=d或d=2R/d。
第一种情况：d=2R/d。枚举a∈[1,sqrt(2R/2d)] <由2*a*a < 2*R/d转变来>，算出对应的b=sqrt(2R/d-a^2)，检查是否此时的A,B满足：A≠B且A,B互质 <根据上面的推理可知必需满足此条件>，若是就将答案加1
第二种情况：d=d。枚举a∈[1,sqrt(d/2)] <由2*a*a < d转变来>，算出对应的b=sqrt(d-a^2)，检查是否此时的A,B满足：A≠B且A,B互质 <根据上面的推理可知必需满足此条件>，若是就将答案加1
因为这样只算出了第一象限的情况<上面枚举时均是从1开始枚举>，根据圆的对称性，其他象限的整点数与第一象限中的整点数相同，最后，在象限轴上的4个整点未算，加上即可，那么最后答案为ans=4*第一象限整点数+4
【时间复杂度分析】：
枚举d：O(sqrt(2R)),然后两次枚举a：O(sqrt(d/2))+O(sqrt(R/d))，求最大公约数：O(logN)
http://hzwer.com/1457.html
http://www.voidcn.com/blog/hbhcy98/article/p-5771408.html
Read full article from BZOJ 1041 [HAOI2008] 圆上的整点 题解与分析 - 初学者 - 博客频道 - CSDN.NET
Output
输出文件为一个正整数, 即圆周上有多少个整点.
Sample Input
4
Sample Output
4
HINT
20%的测试数据, n<=10000.
样例说明：
样例说明：
【分析】：
样例图示：
首先,最暴力的算法显而易见：枚举x轴上的每个点，带入圆的方程，检查是否算出的值是否为整点，这样的枚举量为2*N，显然过不了全点。
然后想数学方法。
有了上面的推理，那么实现的方法为：
枚举d∈[1,sqrt(2R)]，然后根据上述推理可知：必先判d是否为2R的一约数。
此时d为2R的约数有两种情况：d=d或d=2R/d。
第一种情况：d=2R/d。枚举a∈[1,sqrt(2R/2d)] <由2*a*a < 2*R/d转变来>，算出对应的b=sqrt(2R/d-a^2)，检查是否此时的A,B满足：A≠B且A,B互质 <根据上面的推理可知必需满足此条件>，若是就将答案加1
第二种情况：d=d。枚举a∈[1,sqrt(d/2)] <由2*a*a < d转变来>，算出对应的b=sqrt(d-a^2)，检查是否此时的A,B满足：A≠B且A,B互质 <根据上面的推理可知必需满足此条件>，若是就将答案加1
因为这样只算出了第一象限的情况<上面枚举时均是从1开始枚举>，根据圆的对称性，其他象限的整点数与第一象限中的整点数相同，最后，在象限轴上的4个整点未算，加上即可，那么最后答案为ans=4*第一象限整点数+4
【时间复杂度分析】：
枚举d：O(sqrt(2R)),然后两次枚举a：O(sqrt(d/2))+O(sqrt(R/d))，求最大公约数：O(logN)
http://hzwer.com/1457.html
long long R,ans;
long long gcd(long long x,long long y){return x%y==0? y:gcd(y,x%y);}
bool check(long long y,double x)
{
if(x==floor(x))
{
long long x1=(long long)floor(x);
if(gcd(x1*x1,y*y)==1&&x1*x1!=y*y)
return true;
}
return false;
}
int main()
{
scanf("%lld",&R);
for(long long d=1;d<=sqrt(2*R);d++)
{
if((2*R)%d==0)
{
for(long long a=1;a<=(long long)sqrt(2*R/(2*d));a++)
{
double b=sqrt(((2*R)/d)-a*a);
if(check(a,b))ans++;
}
if(d!=(2*R)/d)
{
for(long long a=1;a<=(long long)sqrt(d/2);a++)
{
double b=sqrt(d-a*a);
if(check(a,b))
ans++;
}
}
}
}
printf("%lld",ans*4+4);
return 0;
}
http://edward-mj.com/archives/166
现在给定了一个方程a^2+b^2=c^2 （c已知）
这，就是勾股数。
然后勾股数有一个很霸气的定理。
1、a=m^2-n^2
2、b=2*m*n
3、c=m^2+n^2
4、gcd(n,m)=1。
5、gcd(a,b,c)=1。
同时满足这五条式的是一组勾股数，而且对于所有满足这五条式的(m,n)乘一个k(k>=1)，即(km,kn)。就可以表示所有的勾股数，并且勾股数和三元对(m,n,k)一一对应。
换句话说，每个勾股数都只能表示为一个三元对(m,n,k)。
这，就是勾股数。
然后勾股数有一个很霸气的定理。
1、a=m^2-n^2
2、b=2*m*n
3、c=m^2+n^2
4、gcd(n,m)=1。
5、gcd(a,b,c)=1。
同时满足这五条式的是一组勾股数，而且对于所有满足这五条式的(m,n)乘一个k(k>=1)，即(km,kn)。就可以表示所有的勾股数，并且勾股数和三元对(m,n,k)一一对应。
换句话说，每个勾股数都只能表示为一个三元对(m,n,k)。
好了，现在回到这题的算法上。
我们枚举k^2（程序中是变量：div），但是k这里有一个小技巧，并不需要枚举1<=k^2<=r，
只要枚举1<=k^2<=sqrt(r)即可。因为我们可以保证拆成的两个乘数的大小顺序。
然后枚举了k^2以后，
问题转化成能不能找到一对二元对(m,n)，满足：
1、gcd(m,n)=1
2、m^2+n^2==r/(k^2)
3、gcd(m^2-n^2,2*m*n,m^2+n^2)=1
然后这样暴力还是会很慢的，于是师傅就把第三个条件直接抽出来先判断。
我们可以从：1、3两式推出 r%4=1！
于是直接预先判断，里面那个复杂度为O(sqrt(r))的部分就很少会执行了！
然后算法甚至达到了接近O(sqrt(r))的复杂度。
我们枚举k^2（程序中是变量：div），但是k这里有一个小技巧，并不需要枚举1<=k^2<=r，
只要枚举1<=k^2<=sqrt(r)即可。因为我们可以保证拆成的两个乘数的大小顺序。
然后枚举了k^2以后，
问题转化成能不能找到一对二元对(m,n)，满足：
1、gcd(m,n)=1
2、m^2+n^2==r/(k^2)
3、gcd(m^2-n^2,2*m*n,m^2+n^2)=1
然后这样暴力还是会很慢的，于是师傅就把第三个条件直接抽出来先判断。
我们可以从：1、3两式推出 r%4=1！
于是直接预先判断，里面那个复杂度为O(sqrt(r))的部分就很少会执行了！
然后算法甚至达到了接近O(sqrt(r))的复杂度。
【其它】
时间到了0MS。空间也没用什么。
膜拜AekdyCoin大神。。。
【CODE】
#include#include using namespace std;
int ans=0;
时间到了0MS。空间也没用什么。
膜拜AekdyCoin大神。。。
【CODE】
#include
int ans=0;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
void solve(int r){
if (r==1 || r%4!=1) return;
int m,n;
for (n=1;n*n*2 m=(int)(sqrt(r-n*n)+1e-5);
if (m*m+n*n!=r) continue;
if (gcd(m,n)==1 && m>n) ans++;
}
}
if (r==1 || r%4!=1) return;
int m,n;
for (n=1;n*n*2
if (m*m+n*n!=r) continue;
if (gcd(m,n)==1 && m>n) ans++;
}
}
int main(){
int r,div;
cin >> r;
ans=0;
for (div=1;div*div<=r;div++){
if (r%div) continue;
solve(r/div);
solve(div);
}
ans*=8;
ans+=4;
cout << ans << endl;
}
int r,div;
cin >> r;
ans=0;
for (div=1;div*div<=r;div++){
if (r%div) continue;
solve(r/div);
solve(div);
}
ans*=8;
ans+=4;
cout << ans << endl;
}
Read full article from BZOJ 1041 [HAOI2008] 圆上的整点 题解与分析 - 初学者 - 博客频道 - CSDN.NET
