結果
問題 | No.251 大きな桁の復習問題(1) |
ユーザー |
![]() |
提出日時 | 2018-10-28 03:26:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 36 ms / 5,000 ms |
コード長 | 5,939 bytes |
コンパイル時間 | 2,174 ms |
コンパイル使用メモリ | 210,272 KB |
最終ジャッジ日時 | 2025-01-06 14:57:41 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h>using namespace std;using i64 = int64_t;using vi = vector<i64>;using vvi = vector<vi>;constexpr i64 MOD = 129402307;// 負の数は扱っていない// 宣言するときはconvert関数を使う// 掛け算でFFTをやるので畳み込み後の配列の最大要素を1e13程度にして誤差を小さくしたい// BASELOGを大きくすると桁数が1/BASELOGになる代わりに配列の要素が指数関数的に大きくなる// 掛け算をしないのであれば定数倍早くなるのでBASELOGを大きくするとよい。掛け算をするときは3が精度的に安心constexpr i64 BASE = 1000;constexpr int BASELOG = 3;struct BigInt {// 掛け算のために本来の最大桁数の2倍必要vi digit = vi(1 << 17);int size;BigInt(int size = 1, i64 a = 0) : size(size) {digit[0] = a;}BigInt(const BigInt& a) {size = a.size;digit = vi(a.digit);}};bool operator<(BigInt x, BigInt y) {if (x.size != y.size) {return x.size < y.size;}for (int i = x.size - 1; i >= 0; i--) {if (x.digit[i] != y.digit[i]) {return x.digit[i] < y.digit[i];}}return false;}bool operator>(BigInt x, BigInt y) {return y < x;}bool operator<=(BigInt x, BigInt y) {return !(y < x);}bool operator>=(BigInt x, BigInt y) {return !(x < y);}bool operator!=(BigInt x, BigInt y) {return x < y || y < x;}bool operator==(BigInt x, BigInt y) {return !(x < y) && !(y < x);}BigInt normal(BigInt x, bool all = false) {i64 c = 0;if (all) {x.size = int(x.digit.size()) - 1;}for (int i = 0; i < x.size; i++) {while (x.digit[i] < 0) {x.digit[i + 1] -= 1;x.digit[i] += BASE;}while (x.digit[i] >= BASE) {x.digit[i + 1] += 1;x.digit[i] -= BASE;}i64 a = x.digit[i] + c;x.digit[i] = a % BASE;c = a / BASE;}for (; c > 0; c /= BASE) {x.digit[x.size++] = c % BASE;}while (x.size > 1 && x.digit[x.size - 1] == 0) {x.size--;}return x;}BigInt convert(i64 a) {return normal(BigInt(1, a), true);}BigInt convert(const string& s) {BigInt x;assert(s.size() / BASELOG <= x.digit.size() / 2);int i = s.size() % BASELOG;if (i > 0) {i -= BASELOG;}for (; i < int(s.size()); i += BASELOG) {i64 a = 0;for (int j = 0; j < BASELOG; j++) {a = 10 * a + (i + j >= 0 ? s[i + j] - '0' : 0);}x.digit[x.size++] = a;}reverse(x.digit.begin(), x.digit.begin() + x.size);return normal(x);}ostream &operator<<(ostream& os, BigInt x) {os << x.digit[x.size - 1];for (int i = x.size - 2; i >= 0; i--) {os << setw(BASELOG) << setfill('0') << x.digit[i];}return os;}istream &operator>>(istream& is, BigInt &x) {string s;is >> s;x = convert(s);return is;}string to_string(BigInt &x) {stringstream ss;ss << x.digit[x.size - 1];for (int i = x.size - 2; i >= 0; i--) {ss << setw(BASELOG) << setfill('0') << x.digit[i];}return ss.str();}BigInt operator+(BigInt x, BigInt y) {if (x.size < y.size) {x.size = y.size;}for (int i = 0; i < y.size; i++) {x.digit[i] += y.digit[i];}return normal(x);}BigInt operator-(BigInt x, BigInt y) {assert(x >= y);for (int i = 0; i < y.size; i++) {x.digit[i] -= y.digit[i];}return normal(x);}BigInt operator*(BigInt x, i64 a) {for (int i = 0; i < x.size; i++) {x.digit[i] *= a;}return normal(x);}void fft(vector<complex<double>>& a, bool inv = false) {int n = int(a.size());if (n == 1) return;vector<complex<double>> even(n / 2), odd(n / 2);for (int i = 0; i < n / 2; i++) {even[i] = a[2 * i];odd[i] = a[2 * i + 1];}fft(even, inv);fft(odd, inv);complex<double> omega = polar(1.0, (-2 * inv + 1) * 2 * acos(-1) / n);complex<double> pow_omega = 1.0;for (int i = 0; i < n / 2; i++) {a[i] = even[i] + pow_omega * odd[i];a[i + n / 2] = even[i] - pow_omega * odd[i];pow_omega *= omega;}}void conv(vector<complex<double>>& a, vector<complex<double>>& b) {fft(a);fft(b);int n = int(a.size());for (int i = 0; i < n; i++) {a[i] *= b[i] / complex<double>(n);}fft(a, true);}void conv(vi& a, vi& b) {vector<complex<double>> ac, bc;for (int i = 0; i < a.size(); i++) {ac.push_back(a[i]);bc.push_back(b[i]);}conv(ac, bc);a.resize(ac.size());for (int i = 0; i < ac.size(); i++) {a[i] = long(real(ac[i]) + 0.5);}}BigInt operator*(BigInt x, BigInt y) {conv(x.digit, y.digit);return normal(x, true);}pair<BigInt, i64> divmod(BigInt x, i64 a) {i64 c = 0, t;for (int i = x.size - 1; i >= 0; i--) {t = BASE * c + x.digit[i];x.digit[i] = t / a;c = t % a;}return pair<BigInt, i64>(normal(x), c);}BigInt operator/(BigInt x, i64 a) {return divmod(x, a).first;}i64 operator%(BigInt x, i64 a) {return divmod(x, a).second;}i64 modpow(i64 a, i64 n) {if (n == 0) {return 1;} else if (n % 2 == 0) {i64 t = modpow(a, n / 2);return t * t % MOD;}return a * modpow(a, n - 1) % MOD;}int main() {string n, m;cin >> n >> m;BigInt N = convert(n);BigInt M = convert(m);i64 nn = N % MOD;i64 mm = M % (MOD - 1);if (nn == 0 && mm == 0) {if (m == "0") {cout << 1 << endl;return 0;} else {cout << 0 << endl;return 0;}}cout << modpow(nn, mm) << endl;}