結果
問題 | No.251 大きな桁の復習問題(1) |
ユーザー |
![]() |
提出日時 | 2015-10-13 19:19:18 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 1,436 bytes |
コンパイル時間 | 748 ms |
コンパイル使用メモリ | 74,284 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-12-17 17:29:45 |
合計ジャッジ時間 | 1,511 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
/*フェルマーの小定理Fermat's little theorema^(p-1) == 1 (mod p)pは素数a,pは互いに素N^M == (N % p)^(M % (p-1))p: 素数*/#include <iostream>#include <iomanip>#include <vector>#include <algorithm>#include <cmath>#include <sstream>#define FORR(i,b,e) for(int i=(b);i<(int)(e);++i)#define FOR(i,e) FORR(i,0,e)#define ALL(c) begin(c), end(c)#define sortuniq(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(),v.end()),v.end())#define dump(var) cerr << #var ": " << var << "\n"#define dumpc(con) for(auto& e: con) cerr << e << " "; cerr<<"\n"typedef long long ll;typedef unsigned long long ull;const double EPS = 1e-6;const int d4[] = {0, -1, 0, 1, 0};using namespace std;const ll MOD = 129402307;ll getnum(string &s, ll p) {ll res = 0;for (char &c: s) {res *= 10;res += c - '0';res %= p;}return res;}ll powmod(ll n, ll m, ll p) {ll res = 1;while (m > 0) {if (m & 1) res = (res*n) % p;m /= 2;n = n * n % p;}return res;}ll solve() {ll N, M;string S;cin >> S;if (S == "0") return 0;N = getnum(S, MOD);S.clear();cin >> S;if (S == "0") return 1;M = getnum(S, MOD-1);if (N == 0) return 0;return powmod(N, M, MOD);}int main() {cin.tie(0);ios::sync_with_stdio(false);cout << solve() << endl;return 0;}