#223164 (C++11（廃止可能性あり）) No.613 Solitude by the window

• 問題: No.613 Solitude by the window
• ユーザー: Sebastian King
• 提出日時: 2017-12-13 00:01:27
• 言語: C++11（廃止可能性あり） (gcc 13.3.0)
• 結果: AC
• 実行時間: 1,262 ms / 2,000 ms
• コード長: 1,870 bytes
• コンパイル時間: 1,779 ms
• コンパイル使用メモリ: 159,728 KB
• 実行使用メモリ: 271,872 KB
• 最終ジャッジ日時: 2024-12-14 06:53:22
• 合計ジャッジ時間: 11,153 ms
• ジャッジサーバーID （参考情報）: judge1 / judge5

ファイルパターン	結果
sample	AC * 3
other	AC * 21

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int MM = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e6 + 10;
void prework(){
}
void read(){
}
ll n, P;
ll MAGIC0, MAGIC1;
void precalc(){
    __int128 x = (((__int128)1)<<63) - (((__int128)1)<<63)%P - 1,t;
    for(MAGIC1=0;t=((__int128)1)<<MAGIC1,t<=x*(P-t%P);MAGIC1++);
    if(MAGIC1 < 64) MAGIC1 = 64, t = ((__int128)1)<<64;
    MAGIC0 = (t+P-t%P)/P;
}
long long mod(long long x){
    long long t = ((__int128)x) * MAGIC0 >> 64;
    if (MAGIC0 < 0) t += x;
    return x - (t >> (MAGIC1 - 64)) * P;
}
int f[70000000];
void solve(int casi){
//  cout << "Case #" << casi << ": ";
    cin >> n >> P;
    
    //n=1000000000000000000ll,P=1000000007ll;
    if (P == 2){
        cout << 0 << endl;
        return ;
    }
    //f[0] = 1;
    ll x = 2;
    precalc();
    ll T, G, U;
    int flag = 0;
    n++;
    if (P == MM){
        T = 250000001;
        G = 3;
        U = 192;
        flag = 1;
        goto KKE;
    }
    if (P < 70000000){
        for (int i = 2; i <= n; i++){
            x = mod(x * (x + 4));
            if (f[x]){
                flag = 1;
                T = (i - f[x]);
                G = f[x];
                U = x;
                break;
            }
            else{
                f[x] = i;
            }
        }
    }
    else{
        for (int i = 2; i <= n; i++){
            x = mod(x * (x + 4));
            //cerr << x << ' ' << (x >> 4) <<endl;
            if ((x & 15)==0){
                if (f[x >> 4]){
                    flag = 1;
                    T = (i - f[x >> 4]);
                    G = f[x >> 4];
                    U = x;
                    break;
                }
                else{
                    f[x >> 4] = i;
                }
            }
        }
    }
    KKE:
    //cout << T << endl;
    //cout << flag << ' ' << T << ' ' << G << ' ' << U << endl;
    if (flag){
        x = U;
        ll i = (n - G) % T;
        for (; i; i--){
            x = mod(x * (x + 4));
        }
        cout << x << endl;
    }
    else{
        cout << x << endl;
    }
}
void printans(){
}
int main(){
    std::ios::sync_with_stdio(false);
    prework();
    int T = 1;
//  cin>>T;
    for(int i = 1; i <= T; i++){
        read();
        solve(i);
        printans();
    }
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX