#579843 (C++17) No.1287 えぬけー

• 問題: No.1287 えぬけー
• ユーザー: hamamu
• 提出日時: 2020-11-13 23:16:46
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 6,838 bytes
• コンパイル時間: 2,191 ms
• コンパイル使用メモリ: 200,304 KB
• 最終ジャッジ日時: 2025-01-16 00:03:33
• ジャッジサーバーID （参考情報）: judge5 / judge1

ファイルパターン	結果
sample	AC * 4
other	WA * 1 TLE * 4

ソースコード

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
·#include "bits/stdc++.h"
using namespace std;
using     ll=long long;     using   dd=double;     
using    vll=vector<   ll>; using  vdd=vector< dd>;
using   vvll=vector<  vll>; using vvdd=vector<vdd>;
using  vvvll=vector< vvll>;
using vvvvll=vector<vvvll>;
using   pll=pair<ll,ll>;  using   tll=tuple<ll,ll,ll>; using   qll=tuple<ll,ll,ll,ll>;
using  vpll=vector< pll>; using  vtll=vector< tll>;    using  vqll=vector< qll>;
using vvpll=vector<vpll>; using vvtll=vector<vtll>;    using vvqll=vector<vqll>;
constexpr ll INF = 1LL << 60;
struct Fast{ Fast(){ cin.tie(0); ios::sync_with_stdio(false); cout<<fixed<<setprecision(numeric_limits<double>::max_digits10); } } fast;
#define REPS(i, S, E) for (ll i = (S); i <= (E); i++)
#define REP(i, N) REPS(i, 0, (N)-1)
#define DEPS(i, S, E) for (ll i = (E); i >= (S); i--)
#define DEP(i, N) DEPS(i, 0, (N)-1)
#define rep(i, S, E)  for (ll i = (S); i <= (E); i++)
#define dep(i, E, S)  for (ll i = (E); i >= (S); i--)
#define each(e, v) for (auto&& e : v)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
template<class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; }return false; }
template<class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; }return false; }
template<class T> inline T MaxE(vector<T>&v,ll S,ll E){ T m=v[S]; rep(i,S,E)chmax(m,v[i]); return m; }
template<class T> inline T MinE(vector<T>&v,ll S,ll E){ T m=v[S]; rep(i,S,E)chmin(m,v[i]); return m; }
template<class T> inline T MaxE(vector<T> &v) { return MaxE(v,0,(ll)v.size()-1); }
template<class T> inline T MinE(vector<T> &v) { return MinE(v,0,(ll)v.size()-1); }
template<class T> inline T Sum(vector<T> &v,ll S,ll E){ T s=T(); rep(i,S,E)s+=v[i]; return s; }
template<class T> inline T Sum(vector<T> &v) { return Sum(v,0,v.size()-1); }
template<class T> inline ll sz(T &v){ return (ll)v.size(); }
inline ll CEIL(ll a,ll b){ return (a<0) ? -(-a/b) : (a+b-1)/b; }
inline ll FLOOR(ll a,ll b){ return -CEIL(-a,b); }
template<ll MOD> struct mll_{
    ll val;
    mll_(ll v = 0): val(v % MOD){ if (val < 0) val += MOD; }
    mll_ operator - () const { return -val; }
    mll_ operator + (const mll_ &b) const { return val + b.val; }
    mll_ operator - (const mll_ &b) const { return val - b.val; }
    mll_ operator * (const mll_ &b) const { return val * b.val; }
    mll_ operator / (const mll_ &b) const { return mll_(*this) /= b; }
    mll_ operator + (ll b) const { return *this + mll_(b); }
    mll_ operator - (ll b) const { return *this - mll_(b); }
    mll_ operator * (ll b) const { return *this * mll_(b); }
    friend mll_ operator + (ll a,const mll_ &b) { return b + a; }
    friend mll_ operator - (ll a,const mll_ &b) { return -b + a; }
    friend mll_ operator * (ll a,const mll_ &b) { return b * a; }
    friend mll_ operator / (ll a,const mll_ &b) { return mll_(a)/b; }
    mll_ &operator += (const mll_ &b) { val=(val+b.val)%MOD; return *this; }
    mll_ &operator -= (const mll_ &b) { val=(val+MOD-b.val)%MOD; return *this; }
    mll_ &operator *= (const mll_ &b) { val=(val*b.val)%MOD; return *this; }
    mll_ &operator /= (const mll_ &b) {
        ll c=b.val,d=MOD,u=1,v=0;
        while (d){
            ll t = c / d;
            c -= t * d; swap(c,d);
            u -= t * v; swap(u,v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    mll_ &operator += (ll b) { return *this += mll_(b); }
    mll_ &operator -= (ll b) { return *this -= mll_(b); }
    mll_ &operator *= (ll b) { return *this *= mll_(b); }
    mll_ &operator /= (ll b) { return *this /= mll_(b); }
    bool operator == (const mll_ &b) const { return val == b.val; }
    bool operator != (const mll_ &b) const { return val != b.val; }
    bool operator == (ll b) const { return *this == mll_(b); }
    bool operator != (ll b) const { return *this != mll_(b); }
    friend bool operator == (ll a,const mll_ &b) { return mll_(a) == b.val; }
    friend bool operator != (ll a,const mll_ &b) { return mll_(a) != b.val; }
    friend ostream &operator << (ostream &os,const mll_ &a) { return os << a.val; }
    friend istream &operator >> (istream &is,mll_ &a) { return is >> a.val; }
    static mll_ Combination(ll a,ll b){
        chmin(b,a-b);
        if (b<0) return mll_(0);
        mll_ c = 1;
        rep(i,0,b-1) c *= a-i;
        rep(i,0,b-1) c /= i+1;
        return c;
    }
};
using mll = mll_<1000000006LL>;
using mllb = mll_<1000000007LL>;
using vmll    = std::vector<mll>;
using vvmll   = std::vector<vmll>;
using vvvmll  = std::vector<vvmll>;
using vvvvmll = std::vector<vvvmll>;
template<class T> inline T POW(T a,ll n){ T r=1; for (; n>0; n>>=1,a*=a){ if (n&1)r*=a; } return r; }
inline ll POW(int a,ll n){ return POW((ll)a,n); }
#if 0
#include <atcoder/all>
using namespace atcoder;
#endif
const int MOD = 1000000007;
// 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;
}
const ll M=1000001;
map<long long, long long> apow;
void prep(long long a, int m){
    long long amari = a;
    for (long long r = 1; r < M; ++r) {
        if (!apow.count(amari)) apow[amari] = r;
        (amari *= a) %= m;
    }
}
// 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)} 
#if 0
    map<long long, long long> apow;
    long long amari = a;
    for (long long r = 1; r < sqrtM; ++r) {
        if (!apow.count(amari)) apow[amari] = r;
        (amari *= a) %= m;
    }
#endif
    // check each A^p
    long long A = modpow(modinv(a, m), M, m);
    ll amari = b;
    for (long long q = 0; q < 1000; ++q) {
        if (amari == 1 && q > 0) return q * M;
        else if (apow.count(amari)) return q * M + apow[amari];
        (amari *= A) %= m;
    }
    // no solutions
    return -1;
}
void solve()
{
    //{
    //  rep(i,2,10000000-1){
    //      auto a=POW(mllb(i),2);
    //      if (a==1){
    //          continue;
    //      }
    //      a=POW(mllb(i),500000003);
    //      if (a==1){
    //          continue;
    //      }
    //      cout << i << '\n'; return;
    //  }
    //}
    ll X,K;  cin >> X >> K;
    //10^9+7の原始根 5
    ll x=modlog(5,X,MOD);
    mll xx=x;
    xx/=K;
    mllb ans=POW(mllb(5),xx.val);
    cout << ans << '\n';
}
int main(){
#if 0
    solve();
    //cin2solve();
    //generand();
#else
    ll t;  cin >> t;
    prep(5,MOD);
    rep(i, 0, t-1){
        solve();
        //cin2solve();
    }
#endif
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX