結果
問題 | No.1312 Snake Eyes |
ユーザー |
![]() |
提出日時 | 2020-12-09 12:16:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 146 ms / 2,000 ms |
コード長 | 1,542 bytes |
コンパイル時間 | 2,577 ms |
コンパイル使用メモリ | 196,820 KB |
最終ジャッジ日時 | 2025-01-16 20:43:20 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 85 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) begin(v),end(v) template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; } template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; } using ll = long long; using pii = pair<int, int>; constexpr ll INF = 1ll<<30; constexpr ll longINF = 1ll<<60; constexpr ll MOD = 1000000007; constexpr bool debug = false; //---------------------------------// std::vector<ll> find_divisor(ll n) { assert(n > 0); std::vector<ll> divisor; ll i = 1; for (; i * i <= n; i++) if (n % i == 0) divisor.emplace_back(i); int p = divisor.size() - 1; if (divisor[p] * divisor[p] == n) --p; for (; p >= 0; --p) divisor.emplace_back(n / divisor[p]); return divisor; } int main() { ll N; cin >> N; auto solve = [](ll p, ll n) -> bool { if (p < 2) return false; // p 進法での n auto make = [](ll p, ll n) -> vector<ll> { vector<ll> res; while (n > 0) { res.emplace_back(n % p); n /= p; } reverse(ALL(res)); return res; }; auto num = make(p, n); FOR(i, 1, num.size()) if (num[i - 1] != num[i]) return false; return true; }; ll ans = N + 1; // 1 桁 for (auto d : find_divisor(N)) if (solve(d - 1, N)) chmin(ans, d - 1); // 2 桁 // 3 桁以上(p < sqrt(N)) for (ll i = 1; i * i < N; ++i) if (solve(i, N)) chmin(ans, i); cout << ans << endl; }