记录编号	84615	评测结果	AAAAAAAAAA
题目名称	[SPOJ 1739] Pell方程	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2013-12-16 22:27:57	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<iomanip>
using namespace std;
typedef long long ll;
ll ansp,ansq;
void solve(ll N){
	ll p,lp=1,blp=0;//这一个,前一个和前两个
	ll q,lq=0,blq=1;//这一个,前一个和前两个
	ll a=sqrt((double)N),na;//这一个和下一个
	ll a0=a;
	ll g,lg=0;//这一个和前一个
	ll h,lh=1;//这一个和前一个
	while(true){
		//cout<<"sb"<<endl;
		g=-lg+a*lh;
		h=(N-g*g)/lh;
		na=(g+a0)/h;
		p=a*lp+blp;
		q=a*lq+blq;
		if(p*p-N*q*q==1){
			ansp=p,ansq=q;
			return;
		}
		blp=lp,lp=p;
		blq=lq,lq=q;
		a=na;
		lg=g;
		lh=h;
	}
}
int main(){
	freopen("pell.in","r",stdin);
	freopen("pell.out","w",stdout);
	ll N;
	scanf("%lld",&N);
	solve(N);
	printf("%lld %lld\n",ansp,ansq);
	return 0;
}