結果
問題 | No.435 占い(Extra) |
ユーザー | yosupot |
提出日時 | 2017-09-14 03:47:22 |
言語 | D (dmd 2.106.1) |
結果 |
AC
|
実行時間 | 772 ms / 2,000 ms |
コード長 | 5,112 bytes |
コンパイル時間 | 819 ms |
コンパイル使用メモリ | 104,400 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-12 21:57:49 |
合計ジャッジ時間 | 13,611 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,812 KB |
testcase_01 | AC | 1 ms
6,940 KB |
testcase_02 | AC | 1 ms
6,940 KB |
testcase_03 | AC | 1 ms
6,940 KB |
testcase_04 | AC | 1 ms
6,940 KB |
testcase_05 | AC | 1 ms
6,944 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 1 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,944 KB |
testcase_09 | AC | 2 ms
6,944 KB |
testcase_10 | AC | 8 ms
6,940 KB |
testcase_11 | AC | 8 ms
6,944 KB |
testcase_12 | AC | 73 ms
6,944 KB |
testcase_13 | AC | 73 ms
6,940 KB |
testcase_14 | AC | 74 ms
6,944 KB |
testcase_15 | AC | 74 ms
6,944 KB |
testcase_16 | AC | 77 ms
6,944 KB |
testcase_17 | AC | 119 ms
6,944 KB |
testcase_18 | AC | 72 ms
6,940 KB |
testcase_19 | AC | 71 ms
6,944 KB |
testcase_20 | AC | 715 ms
6,944 KB |
testcase_21 | AC | 724 ms
6,944 KB |
testcase_22 | AC | 712 ms
6,944 KB |
testcase_23 | AC | 717 ms
6,940 KB |
testcase_24 | AC | 720 ms
6,940 KB |
testcase_25 | AC | 763 ms
6,940 KB |
testcase_26 | AC | 705 ms
6,940 KB |
testcase_27 | AC | 718 ms
6,944 KB |
testcase_28 | AC | 1 ms
6,944 KB |
testcase_29 | AC | 720 ms
6,944 KB |
testcase_30 | AC | 716 ms
6,944 KB |
testcase_31 | AC | 583 ms
6,940 KB |
testcase_32 | AC | 632 ms
6,940 KB |
testcase_33 | AC | 722 ms
6,944 KB |
testcase_34 | AC | 772 ms
6,940 KB |
testcase_35 | AC | 719 ms
6,940 KB |
ソースコード
/+ dub.sdl: name "C" dependency "dcomp" version=">=0.6.0" +/ import std.stdio, std.algorithm, std.range, std.conv; // import dcomp.foundation, dcomp.scanner, dcomp.numeric.primitive; int main() { auto sc = new Scanner(stdin); int t; sc.read(t); foreach (_; 0..t) { int n, x, a, b, m; sc.read(n, x, a, b, m); int freq = 1, fac3 = 0; void mul(int x) { while (x % 3 == 0) { x /= 3; fac3++; } freq *= x; freq %= 9; } void div(int x) { while (x % 3 == 0) { x /= 3; fac3--; } auto y = extGcd(x, 9)[0]; freq *= (y + 90) % 9; freq %= 9; } int get() { if (fac3 == 0) return freq; if (fac3 == 1) return (freq*3) % 9; return 0; } int sm, sm9; int r1 = x; foreach (i; 0..n) { int z = r1 % 10; // writeln(z, " ", get()); sm += z; sm9 += get() * z; sm9 %= 9; r1 = ((r1 ^ a) + b) % m; // freq *= (n-1-i) // freq /= i+1 if (i != n-1) { mul(n-1-i); div(i+1); } } // writeln(sm, " ", sm9); if (sm9 == 0 && sm) sm9 += 9; writeln(sm9); } return 0; } /* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/scanner.d */ // module dcomp.scanner; class Scanner { import std.stdio : File; import std.conv : to; import std.range : front, popFront, array, ElementType; import std.array : split; import std.traits : isSomeChar, isStaticArray, isArray; import std.algorithm : map; File f; this(File f) { this.f = f; } char[512] lineBuf; char[] line; private bool succ() { import std.range.primitives : empty, front, popFront; import std.ascii : isWhite; while (true) { while (!line.empty && line.front.isWhite) { line.popFront; } if (!line.empty) break; if (f.eof) return false; line = lineBuf[]; f.readln(line); } return true; } private bool readSingle(T)(ref T x) { import std.algorithm : findSplitBefore; import std.string : strip; import std.conv : parse; if (!succ()) return false; static if (isArray!T) { alias E = ElementType!T; static if (isSomeChar!E) { auto r = line.findSplitBefore(" "); x = r[0].strip.dup; line = r[1]; } else { auto buf = line.split.map!(to!E).array; static if (isStaticArray!T) { assert(buf.length == T.length); } x = buf; line.length = 0; } } else { x = line.parse!T; } return true; } int read(T, Args...)(ref T x, auto ref Args args) { if (!readSingle(x)) return 0; static if (args.length == 0) { return 1; } else { return 1 + read(args); } } } /* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/foundation.d */ // module dcomp.foundation; static if (__VERSION__ <= 2070) { template fold(fun...) if (fun.length >= 1) { auto fold(R, S...)(R r, S seed) { import std.algorithm : reduce; static if (S.length < 2) { return reduce!fun(seed, r); } else { import std.typecons : tuple; return reduce!fun(tuple(seed), r); } } } } version (X86) static if (__VERSION__ < 2071) { import core.bitop : bsf, bsr, popcnt; int bsf(ulong v) { foreach (i; 0..64) { if (v & (1UL << i)) return i; } return -1; } int bsr(ulong v) { foreach_reverse (i; 0..64) { if (v & (1UL << i)) return i; } return -1; } int popcnt(ulong v) { int c = 0; foreach (i; 0..64) { if (v & (1UL << i)) c++; } return c; } } /* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/numeric/primitive.d */ // module dcomp.numeric.primitive; import std.traits; import std.bigint; T pow(T, U)(T x, U n) if (!isFloatingPoint!T && (isIntegral!U || is(U == BigInt))) { return pow(x, n, T(1)); } T pow(T, U)(T x, U n, T e) if (isIntegral!U || is(U == BigInt)) { while (n) { if (n & 1) e *= x; x *= x; n /= 2; } return e; } T lcm(T)(in T a, in T b) { import std.numeric : gcd; return a / gcd(a,b) * b; } T[3] extGcd(T)(in T a, in T b) if (!isIntegral!T || isSigned!T) { if (b==0) { return [T(1), T(0), a]; } else { auto e = extGcd(b, a%b); return [e[1], e[0]-a/b*e[1], e[2]]; } }