2021牛客多校3 E

題目大意：

有 t ( ≤ 1 e 5 ) t(\le 1e5) t(≤1e5)次詢問，每次詢問給定 n ( ≤ 1 e 18 ) n(\le 1e18) n(≤1e18)，給出有多少組 ( x , y ) (x,y) (x,y)滿足 ( x y + 1 ) ∣ ( x 2 + y 2 ) (xy+1)|(x^2+y^2) (xy+1)∣(x2+y2)

解題思路：

• 設 ( x 2 + y 2 ) = k ( x y + 1 ) (x^2 + y^2)=k(xy+1) (x2+y2)=k(xy+1)
• 固定x不懂，由韋達定理，存在另一個 y ′ y' y′滿足 y + y ′ = k x ， y y ′ = x 2 − k y+y'=kx，yy'=x^2-k y+y′=kx，yy′=x2−k 不妨設 x ≤ y x\le y x≤y
• ( x , y ′ ) (x,y') (x,y′)也是一組解，并且 y ′ ≥ 0 , y ′ ≤ y y' \ge 0, y' \le y y′≥0,y′≤y
• 因為方程 x x x和 y y y是對稱的，是以可以設小的 y ′ y' y′為對稱軸，得到更小的 x ′ x' x′和其對應，大概就類似如下圖遞降下去直到 y ′ = 0 y'=0 y′=0

  

• 最後要求 y = k x , k = x 2 y=kx,k=x^2 y=kx,k=x2
• 然後根據這個解再逆推出所有解
• ( x , y ′ ) → ( k x − y ′ , x ) → . . . (x,y')\rightarrow (kx-y',x) \rightarrow... (x,y′)→(kx−y′,x)→...

AC代碼：

#include <bits/stdc++.h>
#define ft first
#define sd second
#define pb push_back
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0) //不能跟puts混用
#define seteps(N) fixed << setprecision(N)
#define endl "\n"
const int maxn = 1e6 + 10;
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
const ll mod = 1e9 + 7;
const ll M = 1e18;
vector <ll> ans;
// __int128 x;
int main() {
	for (ll k = 2; k * k * k <= M; k++) { //k從2開始，是以最後答案要考慮+1，因為k=1沒有考慮
		ll now = k * k * k, pre = k;
		ll t;
		__int128 tmp = k * k;
		while (1) {
			ans.pb(now);
			if (tmp * now - pre > M) break;
			t = now;
			now = tmp * now - pre;
			pre = t;
		}
	}
	sort (ans.begin(), ans.end());
	int t;
	ll n;
	cin >> t;
	while (t--) {
		cin >> n;
		cout << upper_bound(ans.begin(), ans.end(), n) - ans.begin() + 1 << endl;
	}
	
}