记录编号	578009	评测结果	AAAAAAAAAA
题目名称	[SPOJ 1739] Pell方程	最终得分	100
用户昵称	op_组撒头屯	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2023-01-10 09:31:57	内存使用	0.00 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair<int,int>
#define vi vector<int>
#define si set<int>
#define qi queue<int>
#define sti stack<int>
#define fi first
#define se second
#define pb push_back
const int N=10000000+5;
vector<ll>v;
ll calc(ll x,ll lim){
    ll l=1,r=lim;
    while(l<r){
        ll mid=(l+r+1)/2;
        if (mid*mid<=x)l=mid;
        else r=mid-1;
    }
    return l;
}
int main(){
	freopen ("pell.in","r",stdin);
	freopen ("pell.out","w",stdout);
	ll n;scanf("%lld",&n);
	for (ll i=1;i<n;i++){
	    if (i*i%n==1)v.pb(i);
    }
	for (ll k=0;;k++){
	    ll y,s,b;
	    for (int i=0;i<v.size();i++){
	        b=v[i];
	        y=n*k*k+2*k*b+(b*b-1)/n;
	        s=calc(y,k*n+b);
	        if (s*s==y&&s>0&&k*n+b>0){
    	        printf("%lld %lld\n",k*n+b,s);return 0;
            }
        }
    }
    printf("genshin\n");
    return 0;
}