結果
問題 | No.251 大きな桁の復習問題(1) |
ユーザー |
![]() |
提出日時 | 2019-04-14 13:55:38 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 1,614 bytes |
コンパイル時間 | 719 ms |
コンパイル使用メモリ | 30,080 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-18 23:01:54 |
合計ジャッジ時間 | 1,629 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
コンパイルメッセージ
main.c: In function 'ins': main.c:7:14: warning: implicit declaration of function 'getchar_unlocked' [-Wimplicit-function-declaration] 7 | #define gc() getchar_unlocked() | ^~~~~~~~~~~~~~~~ main.c:16:17: note: in expansion of macro 'gc' 16 | do *s = gc(); | ^~ main.c: At top level: main.c:23:18: warning: built-in function 'pow' declared as non-function [-Wbuiltin-declaration-mismatch] 23 | int base[12000], pow[12000]; | ^~~
ソースコード
// yukicoder: No.251 大きな桁の復習問題(1)// 2019.4.14 bal4u#include <stdio.h>#if 1#define gc() getchar_unlocked()#define pc(c) putchar_unlocked(c)#else#define gc() getchar()#define pc(c) putchar(c)#endifint ins(char *s) // 文字列の入力 スペース以下の文字で入力終了{char *p = s;do *s = gc();while (*s++ > ' ');*--s = 0;return s - p;}#define N 1000000000int base[12000], pow[12000];void mpStr2Num(int *num, int w, char *str){char *ss;int *nn;int k, x;if (*str == '0') { *num = 0; return; }ss = str + w;x = 0, k = 1, nn = num;do {x += (*--ss - '0') * k;k *= 10;if (k == N || ss == str) *++nn = x, x = 0, k = 1;} while (ss != str);*num = nn - num;}// 多倍長整数 za を 整数 ab で割ったあまり = za % zbint mpMod(int *za, int zb){int i = *za;int *aa = za + *za;int ca = 0;long long x;while (i--) {x = (long long)N * ca + *aa--;ca = (int)(x % zb);}return ca;}#define MOD 129402307char s[100005];int bigPow(int x, int p){int r = 1;while (p) {if (p & 1) r = (long long)r * x % MOD;x = (long long)x * x % MOD;p >>= 1;}return r;}int main(){int w, b, p;// Nの入力と処理w = ins(s);mpStr2Num(base, w, s);if (base[0] == 0) { puts("0"); return 0; }if (base[0] == 1 && base[1] == 1) { puts("1"); return 0; }// Mの入力と処理w = ins(s);mpStr2Num(pow, w, s);if (pow[0] == 0) { puts("1"); return 0; }if ((b = mpMod(base, MOD)) == 0) { puts("0"); return 0; }p = mpMod(pow, MOD-1);printf("%d\n", bigPow(b, p));return 0;}