#include #include #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") using namespace std; using namespace atcoder; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define repll(i, n) for (long long i = 0; i < (long long)(n); i++) #define rep2(i, n, m) for (int i = n; i < (int)(m); i++) #define repll2(i, n, m) for (long long i = n; i < (long long)(m); i++) #define all(v) v.begin(),v.end() using ll=long long; using ld=long double; using vi=vector; using vvi=vector; using vvvi=vector; using vl=vector; using vvl=vector; using vvvl=vector; using vld=vector; using vvld=vector; int dx[8]={1,0,-1,0,1,1,-1,-1}; int dy[8]={0,1,0,-1,1,-1,1,-1}; const double PI = acos(-1); //const ll MOD=1e9+7; //const ll MOD=998244353; const ll INF=(1LL<<60); const int INF2=(1<<30); //using mint=modint1000000007; //using mint=modint998244353; /* prime_factor(n) 入力:整数 n 出力:nの素因数分解 計算量:O(√n)前後 */ template vector> prime_factor(T n) { vector> ret; for (T i = 2; i * i <= n; i++) { if (n % i != 0) continue; T tmp = 0; while (n % i == 0) { tmp++; n /= i; } ret.push_back(make_pair(i, tmp)); } if (n != 1) ret.push_back(make_pair(n, 1)); return ret; } pair is_square(ll i){ ll low=0,high=i; while(high-low>1){ ll mid=(high+low)/2; if(mid*mid>i)high=mid; else low=mid; } return {(low*low==i),low}; } int main() { ios::sync_with_stdio(false); std::cin.tie(nullptr); int p=-1; /* while(cnt>0){ auto arr=prime_factor(now); int isok=1; for(auto pp:arr){ if(pp.first%4==3){ if(pp.second%2!=0)isok=0; } } if(isok){ if(now+1==p){ cout<1){ ll mid=(high+low)/2; //(now,mid),(mid,now)の距離は? ll d1=now*now+mid*mid; ll d2=(now-mid)*(now-mid)*2; if(d1>d2)high=mid; else low=mid; } ll d1=now*now+low*low; ll d2=(now-low)*(now-low)*2; if(abs(d1-d2)==1){ cout<