結果
問題 |
No.3264 岩井数
|
ユーザー |
![]() |
提出日時 | 2025-09-06 14:53:28 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,846 bytes |
コンパイル時間 | 4,120 ms |
コンパイル使用メモリ | 287,684 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-09-06 14:53:38 |
合計ジャッジ時間 | 6,580 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #ifdef LOCAL #include <debug.hpp> #else #define debug(...) #endif ll naive(ll N) { // 1e15 以下の iwi 数を全探索 string pre, suf, s1, s2; for (ll i = 1e4;; i++) { pre = to_string(i); suf = pre; reverse(suf.begin(), suf.end()); s1 = pre + suf + '9'; s2 = pre + suf.substr(1) + '9'; ll n1 = stoll(s1), n2 = stoll(s2); if (n1 > 1e15 && n2 > 1e15) break; if (n1 % N == 0) return n1; if (n2 % N == 0) return n2; } assert(false); return 0; } void test() { // 100 以下の iwi 数を全探索 string pre, suf, s1, s2; for (ll i = 1; i <= 100; i++) { pre = to_string(i); suf = pre; reverse(suf.begin(), suf.end()); s1 = pre + suf + '9'; s2 = pre + suf.substr(1) + '9'; ll n1 = stoll(s1), n2 = stoll(s2); debug(n1, naive(n1), n2, naive(n2)); } } using i128 = __int128_t; i128 power(i128 x, i128 n) { i128 res = i128{1}; while (n) { if (n & 1) res *= x; x *= x; n >>= 1; } return res; } i128 power(i128 x, i128 n, const i128 mod) { i128 res = i128{1}; x %= mod; while (n) { if (n & 1) res = res * x % mod; x = x * x % mod; n >>= 1; } return res; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); // test(); // N を有限回繋げたものが N の倍数になるのでは? int N; cin >> N; string S = to_string(N), iwi = S; ll mod = 0; while (true) { iwi += S; mod = mod * power(10, ssize(S), N) % N; if (ssize(iwi) > 9 && mod == 0) { cout << iwi << "\n"; return 0; } } }