问题描述:对于方程,其中为素数,x,y为整数,且,输出符合条件的x,y。
分析:对于本方程,我们通过费马平方和定理知道,只有奇素数p满足这个条件时才有解。
那么当此方程有解时,解有几个呢?很明显不可能存在解满足x等于y的情况,那么不妨设,那么本方程解唯一。
现在我们就来求满足此条件的x,y,方法分为两步:
(1)先找出同余方程的最小正整数解。(关于这个问题我的上一篇文章已经做了细致的分析)
(2)对和进行欧几里德辗转相除运算,记每次的余数为,当满足条件时停止运算,此时的就是x
这样就得到了x,那么y可以通过得到,问题解决。
或者这样看着不爽,因为有开根号,那么我们可以发现其实这里的y就是在辗转相除的时候把中所有的q累加起来
的结果。 本方法是目前为止发现解此问题最快的方法。
假设已经求出了,那么如下代码就是求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;
}