結果
問題 | No.1255 ハイレーツ・オブ・ボリビアン |
ユーザー |
![]() |
提出日時 | 2020-10-09 22:56:47 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,285 bytes |
コンパイル時間 | 2,061 ms |
コンパイル使用メモリ | 200,580 KB |
最終ジャッジ日時 | 2025-01-15 05:35:44 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 1 WA * 13 TLE * 1 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define int long long #define rep(i, n) for (int i = 0; i < (int) (n); i++) #define reps(i, n) for (int i = 1; i <= (int) (n); i++) #define all(a) (a).begin(), (a).end() #define uniq(a) (a).erase(unique(all(a)), (a).end()) #define bit(n) (1LL << (n)) #define dump(a) cerr << #a " = " << (a) << endl using vint = vector<int>; using pint = pair<int, int>; using vpint = vector<pint>; template<typename T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>; constexpr double PI = 3.1415926535897932384626433832795028; constexpr int DY[9] = {0, 1, 0, -1, 1, 1, -1, -1, 0}; constexpr int DX[9] = {1, 0, -1, 0, 1, -1, -1, 1, 0}; int sign(int a) { return (a > 0) - (a < 0); } int cdiv(int a, int b) { return (a - 1 + b) / b; } template<typename T> void fin(T a) { cout << a << endl; exit(0); } template<typename T> T sq(T a) { return a * a; } template<typename T, typename U> bool chmax(T &a, const U &b) { if (a < b) { a = b; return true; } return false; } template<typename T, typename U> bool chmin(T &a, const U &b) { if (b < a) { a = b; return true; } return false; } template<typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &a) { os << "(" << a.first << ", " << a.second << ")"; return os; } template<typename T> ostream &operator<<(ostream &os, const vector<T> &a) { os << "{"; for (auto itr = a.begin(); itr != a.end(); itr++) { os << *itr << (next(itr) != a.end() ? ", " : ""); } os << "}"; return os; } template<typename T> ostream &operator<<(ostream &os, const deque<T> &a) { os << "{"; for (auto itr = a.begin(); itr != a.end(); itr++) { os << *itr << (next(itr) != a.end() ? ", " : ""); } os << "}"; return os; } template<typename T> ostream &operator<<(ostream &os, const set<T> &a) { os << "{"; for (auto itr = a.begin(); itr != a.end(); itr++) { os << *itr << (next(itr) != a.end() ? ", " : ""); } os << "}"; return os; } template<typename T> ostream &operator<<(ostream &os, const multiset<T> &a) { os << "{"; for (auto itr = a.begin(); itr != a.end(); itr++) { os << *itr << (next(itr) != a.end() ? ", " : ""); } os << "}"; return os; } template<typename T, typename U> ostream &operator<<(ostream &os, const map<T, U> &a) { os << "{"; for (auto itr = a.begin(); itr != a.end(); itr++) { os << *itr << (next(itr) != a.end() ? ", " : ""); } os << "}"; return os; } struct setup { static constexpr int PREC = 20; setup() { cout << fixed << setprecision(PREC); cerr << fixed << setprecision(PREC); }; } setup; // a^b long long modpow(long long a, long long n, long long mod) { long long res = 1; while (n > 0) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } // a^-1 long long modinv(long long a, long long m) { long long b = m, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= m; if (u < 0) u += m; return u; } // a^x ≡ b (mod. m) となる最小の正の整数 x を求める long long modlog(long long a, long long b, int m) { a %= m, b %= m; // calc sqrt{M} long long lo = -1, hi = m; while (hi - lo > 1) { long long mid = (lo + hi) / 2; if (mid * mid >= m) hi = mid; else lo = mid; } long long sqrtM = hi; // {a^0, a^1, a^2, ..., a^sqrt(m)} map<long long, long long> apow; long long amari = 1; for (long long r = 0; r < sqrtM; ++r) { if (!apow.count(amari)) apow[amari] = r; (amari *= a) %= m; } // check each A^p long long A = modpow(modinv(a, m), sqrtM, m); amari = b; for (long long q = 0; q < sqrtM; ++q) { if (apow.count(amari)) { long long res = q * sqrtM + apow[amari]; if (res > 0) return res; } (amari *= A) %= m; } // no solutions return -1; } signed main() { int T; cin >> T; while (T--) { int N; cin >> N; cout << modlog(2, 1, 2 * N - 1) << endl; } }