結果
問題 | No.613 Solitude by the window |
ユーザー |
![]() |
提出日時 | 2017-12-13 04:13:44 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,858 ms / 2,000 ms |
コード長 | 2,249 bytes |
コンパイル時間 | 1,858 ms |
コンパイル使用メモリ | 115,472 KB |
実行使用メモリ | 393,856 KB |
最終ジャッジ日時 | 2024-12-14 07:59:27 |
合計ジャッジ時間 | 11,252 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#pragma GCC optimize ("O3")#include <iostream>#include <iomanip>#include <cstdio>#include <cstdlib>#include <cstring>#include <cassert>#include <algorithm>#include <numeric>#include <random>#include <vector>#include <array>#include <bitset>#include <queue>#include <set>#include <unordered_set>#include <map>#include <unordered_map>using namespace std;using uint = unsigned int;using ll = long long;using ull = unsigned long long;constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); }template<class T> using V = vector<T>;template<class T> using VV = V<V<T>>;struct rng {struct A {int n;const bool operator!=(A r) { return n != r.n; }A& operator++() { n++; return *this; }int operator*() { return n; }};int l, r;rng(int r) : l(0), r(max(0, r)) {}rng(int l, int r) : l(l), r(max(l, r)) {}A begin() { return A{l}; }A end() { return A{r}; }};const int MD = TEN(9) + TEN(8) + 10;uint md; ull imd;inline ull nx(ull x) {ull y = ull(x) * (x) - 2;ull d = (__int128(y) * imd) >> 64;return y - d * md;}ull naive(ll n) {ull s = 4;for (int i = 0; i < n; i++) {s = nx(s);}return s;}ull big(ull n) {ull s = 4;for (int i = 0; i < 100; i++) s = nx(s);ull t = s;n -= 100;uint c = 0;uint d = 0;static const uint B = TEN(8) / 2;V<ull> buf(B);while (c < n) {buf[d] = s;s = nx(s);c++;d++;if (d == B) d = 0;if (__builtin_expect(s == t, 0)) {n %= c;// cerr << c << " " << n << endl;if (c - n < B) {// cerr << d << " " << ((d + TEN(8) - (c - n)) % TEN(8)) << endl;return buf[(d + B - (c - n)) % B];}c = 0;}}return s;}int main() {cin.tie(0);ios::sync_with_stdio(false);cout << setprecision(20);ll n;cin >> n >> md;if (md == 2) {cout << 0 << endl;return 0;}imd = ((__int128(1)<<64) + md-1) / md;ull ans;if (n < 1000) ans = naive(n);else ans = big(n);ans = (ans + md - 2) % md;cout << ans << endl;return 0;}