結果
問題 | No.251 大きな桁の復習問題(1) |
ユーザー | te-sh |
提出日時 | 2017-05-26 10:44:17 |
言語 | D (dmd 2.107.1) |
結果 |
AC
|
実行時間 | 131 ms / 5,000 ms |
コード長 | 1,889 bytes |
コンパイル時間 | 986 ms |
コンパイル使用メモリ | 91,256 KB |
実行使用メモリ | 4,380 KB |
最終ジャッジ日時 | 2023-09-03 13:37:13 |
合計ジャッジ時間 | 3,150 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 1 ms
4,376 KB |
testcase_04 | AC | 1 ms
4,376 KB |
testcase_05 | AC | 1 ms
4,380 KB |
testcase_06 | AC | 1 ms
4,376 KB |
testcase_07 | AC | 1 ms
4,376 KB |
testcase_08 | AC | 1 ms
4,380 KB |
testcase_09 | AC | 130 ms
4,376 KB |
testcase_10 | AC | 130 ms
4,376 KB |
testcase_11 | AC | 131 ms
4,376 KB |
testcase_12 | AC | 131 ms
4,376 KB |
testcase_13 | AC | 131 ms
4,380 KB |
testcase_14 | AC | 131 ms
4,376 KB |
testcase_15 | AC | 130 ms
4,376 KB |
testcase_16 | AC | 130 ms
4,380 KB |
testcase_17 | AC | 130 ms
4,376 KB |
testcase_18 | AC | 130 ms
4,380 KB |
testcase_19 | AC | 130 ms
4,376 KB |
testcase_20 | AC | 2 ms
4,376 KB |
testcase_21 | AC | 2 ms
4,376 KB |
testcase_22 | AC | 2 ms
4,380 KB |
testcase_23 | AC | 1 ms
4,380 KB |
ソースコード
import std.algorithm, std.conv, std.range, std.stdio, std.string; import std.bigint; // BigInt const p = 129402307; alias FactorRing!p mint; void main() { auto nb = readln.chomp.to!BigInt; auto mb = readln.chomp.to!BigInt; if (nb == 0) { writeln(0); return; } if (mb == 0) { writeln(1); return; } auto n = mint((nb % p).to!int); auto m = (mb % (p - 1)).to!int; if (n == 0) { writeln(0); } else { writeln(repeatedSquare(n, m).to!int); } } T repeatedSquare(T, alias pred = "a * b", U)(T a, U n) { return repeatedSquare(a, n, T(1)); } T repeatedSquare(T, alias pred = "a * b", U)(T a, U n, T init) { import std.functional; alias predFun = binaryFun!pred; if (n == 0) return init; auto r = init; while (n > 0) { if ((n & 1) == 1) r = predFun(r, a); a = predFun(a, a); n >>= 1; } return r; } struct FactorRing(int m) { int _m = m; long v; @property int toInt() { return v.to!int; } alias toInt this; this(T)(T _v) { v = mod(_v); } ref FactorRing!m opAssign(int _v) { v = mod(_v); return this; } pure auto mod(long _v) const { return (_v % m + m) % m; } pure auto opBinary(string op: "+")(int rhs) const { return FactorRing!m(v + rhs); } pure auto opBinary(string op: "-")(int rhs) const { return FactorRing!m(v - rhs); } pure auto opBinary(string op: "*")(int rhs) const { return FactorRing!m(v * rhs); } pure auto opBinary(string op)(FactorRing!m rhs) const if (op == "+" || op == "-" || op == "*") { return opBinary!op(rhs.v); } auto opOpAssign(string op: "+")(int rhs) { v = mod(v + rhs); } auto opOpAssign(string op: "-")(int rhs) { v = mod(v - rhs); } auto opOpAssign(string op: "*")(int rhs) { v = mod(v * rhs); } auto opOpAssign(string op)(FactorRing!m rhs) if (op == "+" || op == "-" || op == "*") { return opOpAssign!op(rhs.v); } }