結果
| 問題 | No.1648 Sum of Powers |
| ユーザー |
 SSRS
|
| 提出日時 | 2021-08-13 22:41:31 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 2,667 bytes |
| コンパイル時間 | 2,476 ms |
| コンパイル使用メモリ | 195,016 KB |
| 実行使用メモリ | 16,384 KB |
| 最終ジャッジ日時 | 2024-10-03 20:46:21 |
| 合計ジャッジ時間 | 6,284 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 74 ms
16,384 KB |
| testcase_01 | AC | 29 ms
5,248 KB |
| testcase_02 | WA | - |
| testcase_03 | TLE | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
ソースコード
#include <bits/stdc++.h>
using namespace std;
const int SQRT = 100000;
const long long MOD = 998244353;
long long modpow(long long a, long long b){
long long ans = 1;
while (b > 0){
if (b % 2 == 1){
ans *= a;
ans %= MOD;
}
a *= a;
a %= MOD;
b /= 2;
}
return ans;
}
long long modinv(long long a){
return modpow(a, MOD - 2);
}
vector<vector<long long>> matmul(vector<vector<long long>> A, vector<vector<long long>> B){
int N = A.size();
vector<vector<long long>> ans(N, vector<long long>(N, 0));
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++){
for (int k = 0; k < N; k++){
ans[i][k] += A[i][j] * B[j][k];
ans[i][k] %= MOD;
}
}
}
return ans;
}
vector<vector<long long>> matexp(vector<vector<long long>> A, long long b){
int N = A.size();
vector<vector<long long>> ans(N, vector<long long>(N, 0));
for (int i = 0; i < N; i++){
ans[i][i] = 1;
}
while (b > 0){
if (b % 2 == 1){
ans = matmul(ans, A);
}
A = matmul(A, A);
b /= 2;
}
return ans;
}
int main(){
int A, B, P, Q;
cin >> A >> B >> P >> Q;
if (B == 0){
if (A == 0){
cout << 2 << endl;
} else {
vector<long long> a(SQRT);
a[0] = P;
for (int i = 0; i < SQRT - 1; i++){
a[i + 1] = a[i] * modinv(A) % MOD;
}
map<long long, int> mp;
for (int i = 0; i < SQRT; i++){
mp[a[i]] = i;
}
long long A2 = modpow(A, SQRT);
long long X = A * A % MOD, N = 2;
while (true){
if (mp.count(X) == 1){
cout << N + mp[X] << endl;
break;
}
X *= A2;
X %= MOD;
N += SQRT;
}
}
} else {
vector<vector<long long>> C = {{A, MOD - B}, {1, 0}};
vector<vector<long long>> Cinv = {{0, 1}, {(MOD - 1) * modinv(B) % MOD, A * modinv(B) % MOD}};
vector<pair<long long, long long>> a(SQRT);
vector<vector<long long>> tmp = {{1, 0}, {0, 1}};
a[0] = make_pair(P, Q);
for (int i = 0; i < SQRT - 1; i++){
tmp = matmul(tmp, Cinv);
a[i + 1] = make_pair((tmp[0][0] * P + tmp[0][1] * Q) % MOD, (tmp[1][0] * P + tmp[1][1] * Q) % MOD);
}
map<pair<long long, long long>, int> mp;
for (int i = 0; i < SQRT; i++){
mp[a[i]] = i;
}
vector<vector<long long>> C2 = matexp(C, SQRT);
long long X = (A * A - B * 2 + MOD % MOD) % MOD, Y = A;
long long N = 2;
while (true){
if (mp.count(make_pair(X, Y)) == 1){
cout << N + mp[make_pair(X, Y)] << endl;
break;
}
long long X2 = (C2[0][0] * X + C2[0][1] * Y) % MOD;
long long Y2 = (C2[1][0] * X + C2[1][1] * Y) % MOD;
X = X2;
Y = Y2;
N += SQRT;
}
}
}