关于方程x^2+y^2=p (p为素数)的解问题

问题描述:对于方程关于方程x^2+y^2=p (p为素数)的解问题,其中关于方程x^2+y^2=p (p为素数)的解问题为素数,x,y为整数,且关于方程x^2+y^2=p (p为素数)的解问题,输出符合条件的x,y。

分析:对于本方程,我们通过费马平方和定理知道,只有奇素数p满足关于方程x^2+y^2=p (p为素数)的解问题这个条件时才有解。

那么当此方程有解时,解有几个呢?很明显不可能存在解满足x等于y的情况,那么不妨设关于方程x^2+y^2=p (p为素数)的解问题,那么本方程解唯一。

现在我们就来求满足此条件的x,y,方法分为两步:

(1)先找出同余方程关于方程x^2+y^2=p (p为素数)的解问题的最小正整数解关于方程x^2+y^2=p (p为素数)的解问题。(关于这个问题我的上一篇文章已经做了细致的分析)

(2)对关于方程x^2+y^2=p (p为素数)的解问题关于方程x^2+y^2=p (p为素数)的解问题进行欧几里德辗转相除运算,记每次的余数为关于方程x^2+y^2=p (p为素数)的解问题,当满足条件关于方程x^2+y^2=p (p为素数)的解问题时停止运算,此时的关于方程x^2+y^2=p (p为素数)的解问题就是x

这样就得到了x,那么y可以通过关于方程x^2+y^2=p (p为素数)的解问题得到,问题解决。

或者这样看着不爽,因为有开根号,那么我们可以发现其实这里的y就是在辗转相除的时候把关于方程x^2+y^2=p (p为素数)的解问题中所有的q累加起来

的结果。 本方法是目前为止发现解此问题最快的方法。

假设已经求出了关于方程x^2+y^2=p (p为素数)的解问题,那么如下代码就是求x,y的:

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <math.h> using namespace std;
typedef long long LL; void Solve(LL a,LL b)
{
LL r=a%b,t=a;
LL ans=a/b;
while(r*r>=t)
{
a=b;
b=r;
r=a%b;
ans+=a/b;
}
if(r>ans) swap(r,ans);
cout<<r<<" "<<ans<<endl;
} int main()
{
LL p,x0;
while(cin>>p>>x0)
{
Solve(p,x0);
}
return 0;
}
上一篇:jdbc escape


下一篇:WinForm