// 基本テンプレート #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++) #define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++) #define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--) #define debug(...) fprintf(stderr, __VA_ARGS__) #define int long long int template void chmax(T &a, T b) {a = max(a, b);} template void chmin(T &a, T b) {a = min(a, b);} template void chadd(T &a, T b) {a = a + b;} typedef pair pii; typedef long long ll; int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; const ll INF = 1001001001001001LL; const ll MOD = 1000000007LL; struct Elem { long double sum; vector nums; bool operator<(const Elem &e) const { return sum < e.sum; } }; // [lb, ub] の閉区間内の値をランダムに返す構造体 // #include しよう struct Rand { public: Rand() = default; Rand(std::mt19937::result_type seed) : eng(seed) {} int NextInt(int lb, int ub) { return std::uniform_int_distribution{lb, ub}(eng); } ll NextLong(ll lb, ll ub) { return std::uniform_int_distribution{lb, ub}(eng); } double NextDouble(double lb, double ub) { return std::uniform_real_distribution{lb, ub}(eng); } private: std::mt19937 eng{std::random_device{}()}; }; Rand rnd(114514); pair< vector, bool > solve(long double target) { vector cand; long double T = target / 8; long double EPS = 1e-4; // target / 8 に近いもの for(int i=0; i<100; ) { int P = (int)T; int B = rnd.NextInt(0, P*P); long double rest = T - sqrtl(B); long double flt_A = rest * rest; for(int k=0; k<2; k++) { int A = (int)flt_A + k; long double sum = sqrtl(A) + sqrtl(B); if(abs(sum - T) < EPS) { cand.push_back(Elem{sum, vector{A, B}}); i++; } } } for(int i=0; i<3; i++) { T *= 2, EPS *= 1e-2; sort(cand.begin(), cand.end()); vector nxt_cand; for(size_t k=0; k()}) - cand.begin(); // printf("lb = %Lf, ub = %Lf, it = %lld\n", lb, ub, it); for(int j=-1; j<2; j++) { int x = it - j; if(x < 0 || x >= cand.size()) continue; long double val = cand[k].sum + cand[x].sum; // printf("val = %Lf, T = %Lf\n", val, T); if(abs(val - T) < EPS) { vector nxt_vec; copy(cand[k].nums.begin(), cand[k].nums.end(), back_inserter(nxt_vec)); copy(cand[x].nums.begin(), cand[x].nums.end(), back_inserter(nxt_vec)); nxt_cand.push_back(Elem{val, nxt_vec}); } } } swap(cand, nxt_cand); } if(cand.size() > 0) { return make_pair(cand[0].nums, true); } else { return make_pair(vector(), false); } } signed main() { int Q; scanf("%lld", &Q); for(int t=0; t ans; bool found = false; while(1) if(tie(ans, found) = solve(P), found) break; // solve(P); printf("%zu\n", ans.size()); for(size_t i=0; i