結果

問題 No.3102 floor sqrt xor
ユーザー ecottea
提出日時 2025-04-11 22:25:19
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 8,122 bytes
コンパイル時間 4,247 ms
コンパイル使用メモリ 258,300 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-04-11 22:25:24
合計ジャッジ時間 5,117 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifndef HIDDEN_IN_VS // 折りたたみ用

// 警告の抑制
#define _CRT_SECURE_NO_WARNINGS

// ライブラリの読み込み
#include <bits/stdc++.h>
using namespace std;

// 型名の短縮
using ll = long long; using ull = unsigned long long; // -2^63 ～ 2^63 = 9e18（int は -2^31 ～ 2^31 = 2e9）
using pii = pair<int, int>;	using pll = pair<ll, ll>;	using pil = pair<int, ll>;	using pli = pair<ll, int>;
using vi = vector<int>;		using vvi = vector<vi>;		using vvvi = vector<vvi>;	using vvvvi = vector<vvvi>;
using vl = vector<ll>;		using vvl = vector<vl>;		using vvvl = vector<vvl>;	using vvvvl = vector<vvvl>;
using vb = vector<bool>;	using vvb = vector<vb>;		using vvvb = vector<vvb>;
using vc = vector<char>;	using vvc = vector<vc>;		using vvvc = vector<vvc>;
using vd = vector<double>;	using vvd = vector<vd>;		using vvvd = vector<vvd>;
template <class T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
using Graph = vvi;

// 定数の定義
const double PI = acos(-1);
int DX[4] = { 1, 0, -1, 0 }; // 4 近傍（下，右，上，左）
int DY[4] = { 0, 1, 0, -1 };
int INF = 1001001001; ll INFL = 4004004003094073385LL; // (int)INFL = INF, (int)(-INFL) = -INF;

// 入出力高速化
struct fast_io { fast_io() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } } fastIOtmp;

// 汎用マクロの定義
#define all(a) (a).begin(), (a).end()
#define sz(x) ((int)(x).size())
#define lbpos(a, x) (int)distance((a).begin(), std::lower_bound(all(a), (x)))
#define ubpos(a, x) (int)distance((a).begin(), std::upper_bound(all(a), (x)))
#define Yes(b) {cout << ((b) ? "Yes\n" : "No\n");}
#define rep(i, n) for(int i = 0, i##_len = int(n); i < i##_len; ++i) // 0 から n-1 まで昇順
#define repi(i, s, t) for(int i = int(s), i##_end = int(t); i <= i##_end; ++i) // s から t まで昇順
#define repir(i, s, t) for(int i = int(s), i##_end = int(t); i >= i##_end; --i) // s から t まで降順
#define repe(v, a) for(const auto& v : (a)) // a の全要素（変更不可能）
#define repea(v, a) for(auto& v : (a)) // a の全要素（変更可能）
#define repb(set, d) for(int set = 0, set##_ub = 1 << int(d); set < set##_ub; ++set) // d ビット全探索（昇順）
#define repis(i, set) for(int i = lsb(set), bset##i = set; i < 32; bset##i -= 1 << i, i = lsb(bset##i)) // set の全要素（昇順）
#define repp(a) sort(all(a)); for(bool a##_perm = true; a##_perm; a##_perm = next_permutation(all(a))) // a の順列全て（昇順）
#define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());} // 重複除去
#define EXIT(a) {cout << (a) << endl; exit(0);} // 強制終了
#define inQ(x, y, u, l, d, r) ((u) <= (x) && (l) <= (y) && (x) < (d) && (y) < (r)) // 半開矩形内判定

// 汎用関数の定義
template <class T> inline ll powi(T n, int k) { ll v = 1; rep(i, k) v *= n; return v; }
template <class T> inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; } // 最大値を更新（更新されたら true を返す）
template <class T> inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; } // 最小値を更新（更新されたら true を返す）
template <class T> inline T getb(T set, int i) { return (set >> i) & T(1); }
template <class T> inline T smod(T n, T m) { n %= m; if (n < 0) n += m; return n; } // 非負mod

// 演算子オーバーロード
template <class T, class U> inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template <class T> inline istream& operator>>(istream& is, vector<T>& v) { repea(x, v) is >> x; return is; }
template <class T> inline vector<T>& operator--(vector<T>& v) { repea(x, v) --x; return v; }
template <class T> inline vector<T>& operator++(vector<T>& v) { repea(x, v) ++x; return v; }

#endif // 折りたたみ用


#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;

#ifdef _MSC_VER
#include "localACL.hpp"
#endif

using mint = modint998244353;
//using mint = static_modint<(int)1e9 + 7>;
//using mint = modint; // mint::set_mod(m);

namespace atcoder {
	inline istream& operator>>(istream& is, mint& x) { ll x_; is >> x_; x = x_; return is; }
	inline ostream& operator<<(ostream& os, const mint& x) { os << x.val(); return os; }
}
using vm = vector<mint>; using vvm = vector<vm>; using vvvm = vector<vvm>; using vvvvm = vector<vvvm>; using pim = pair<int, mint>;
#endif


#ifdef _MSC_VER // 手元環境（Visual Studio）
#include "local.hpp"
#else // 提出用（gcc）
inline int popcount(int n) { return __builtin_popcount(n); }
inline int popcount(ll n) { return __builtin_popcountll(n); }
inline int lsb(int n) { return n != 0 ? __builtin_ctz(n) : 32; }
inline int lsb(ll n) { return n != 0 ? __builtin_ctzll(n) : 64; }
inline int msb(int n) { return n != 0 ? (31 - __builtin_clz(n)) : -1; }
inline int msb(ll n) { return n != 0 ? (63 - __builtin_clzll(n)) : -1; }
#define dump(...)
#define dumpel(v)
#define dump_math(v)
#define input_from_file(f)
#define output_to_file(f)
#define Assert(b) { if (!(b)) { vc MLE(1<<30); EXIT(MLE.back()); } } // RE の代わりに MLE を出す
#endif


//【整数平方根】O(1)
/*
* 非負の数 a の平方根の切り捨て値を返す．
*
* 制約：コンパイラが gcc
*/
template <class T>
T integer_sqrt(T a) {
	//【備考】
	// double 精度だと，N = 622046740405562316 で
	//		(int)sqrt(N) = 788699398 != 788699397 = floor(√N)
	// となってしまった．

	return (T)sqrtl((long double)a);
}


void zikken() {
	int n = 5000;

	vi res;

	repi(k, 1, n) {
		auto x = integer_sqrt(k);
		res.push_back(x ^ k);
		//dump(x ^ k);
	}
	uniq(res);
	//dump(res);

	vi a(n - 100);
	iota(all(a), 0);

	vi b;
	set_difference(all(a), all(res), inserter(b, b.end()));
	dump(b);

	repe(x, b) {
		dump(bitset<16>(x));
	}

	exit(0);
}
/*
1 11 29 55 89 115 165 239 305 379 429 519 617 707 853 991 1121 1259 1405 1495 1721 1811 1989 2191 2385 2587 2765 3047 3209 3491 3765 4031 4289 4555 4829
0000000000000001
0000000000001011
0000000000011101
0000000000110111
0000000001011001
0000000001110011
0000000010100101
0000000011101111
0000000100110001
0000000101111011
0000000110101101
0000001000000111
0000001001101001
0000001011000011
0000001101010101
0000001111011111
0000010001100001
0000010011101011
0000010101111101
0000010111010111
0000011010111001
0000011100010011
0000011111000101
0000100010001111
0000100101010001
0000101000011011
0000101011001101
0000101111100111
0000110010001001
0000110110100011
0000111010110101
0000111110111111
0001000011000001
0001000111001011
0001001011011101
*/


void zikken2() {
	int n = 50;

	vi res;

	repi(k, 1, n) {
		auto x = integer_sqrt(k);
		dump(bitset<8>(x), bitset<8>(k));
	}

	exit(0);
}


void Main() {
	ll n;
	cin >> n;

	dump(bitset<64>(n));

	//if (n <= (ll)1e4) {
	//	repi(k, 0, 2 * n) {
	//		auto rk = integer_sqrt(k);
	//		if ((rk ^ k) == n) {
	//			cout << k << "\n";
	//			return;
	//		}
	//	}
	//}

	int b = (msb(n) + 2) / 2;
	dump("b:", b);

	ll k = (n >> b) << b;
	dump("k:", k, bitset<64>(k));

	while (b >= 10) {
		ll kl = k;
		ll kr = k + (1LL << b) - 1;
		dump(kl, kr, bitset<64>(kl), bitset<64>(kr));

		auto sl = integer_sqrt(kl);
		auto sr = integer_sqrt(kr);
		dump(sl, sr, bitset<64>(sl), bitset<64>(sr));

		if (sl == sr) {
			repir(b2, b - 1, 0) {
				k ^= (getb(n, b2) ^ getb(sl, b2)) << b2;
				b = b2;
			}

			auto rk = integer_sqrt(k);
			if ((rk ^ k) == n) {
				cout << k << "\n";
				return;
			}
			else {
				cout << -1 << "\n";
				return;
			}
		}

		repir(b2, b - 1, 0) {
			if (getb(sl, b2) != getb(sr, b2)) break;

			k ^= (getb(n, b2) ^ getb(sl, b2)) << b2;
			b = b2;
		}

		dump("b:", b);
		dump("k:", k, bitset<64>(k));
	}

	rep(hoge, 1024) {
		auto rk = integer_sqrt(k);
		if ((rk ^ k) == n) {
			cout << k << "\n";
			return;
		}

		k++;
	}

	cout << -1 << "\n";
}

int main() {
//	input_from_file("input.txt");
//	output_to_file("output.txt");

	int t = 1;
	cin >> t; // マルチテストケースの場合

	while (t--) {
		dump("------------------------------");
		Main();
	}
}
0