[BZOJ1041 [HAOI2008]圆上的整点]数论、勾股数相关定理

【题目地址】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1041
【算法分析】
以下内容来自师傅AekdyCoin的blog以及口授
现在给定了一个方程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)。

好了，现在回到这题的算法上。
我们枚举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;

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++;
}
}

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;
}