結果
問題 | No.3006 ベイカーの問題 |
ユーザー |
![]() |
提出日時 | 2025-01-10 22:42:01 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 3,665 bytes |
コンパイル時間 | 687 ms |
コンパイル使用メモリ | 86,940 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2025-01-11 17:00:20 |
合計ジャッジ時間 | 1,845 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
import std.algorithm, std.array, std.conv, std.stdio, std.typecons; immutable p = 998244353; alias F = FiniteField!p; // x + y \sqrt{-5} struct Int { F x, y; this (long x, long y) { this.x = F(x); this.y = F(y); } this (F x, F y) { this.x = x; this.y = y; } Int opBinary(string op)(Int rhs) { auto result = this; static if (op == "+") { result.x += rhs.x; result.y += rhs.y; } else if (op == "-") { result.x -= rhs.x; result.y -= rhs.y; } else if (op == "*") { result.x = this.x*rhs.x - this.y*rhs.y*5; result.y = this.x*rhs.y + this.y*rhs.x; } else assert(0); return result; } Int opOpAssign(string op)(Int rhs) { mixin("this = this"~op~"rhs; return this;"); } Int conjugate() { auto result = this; result.y = -result.y; return result; } } Int power(Int a, ulong N) { Int a_pow_N = Int(1, 0); Int pow = a; // a^(2^i) int i = 0; while (N > 0) { if (N%2 == 1) a_pow_N *= pow; i++; pow *= pow; N >>= 1; } return a_pow_N; } auto solve(Int a, ulong N) { if (a.x == F(1) && a.y == F(0)) return Int(N, 0); else return (a.power(N) - Int(1, 0)) * (a - Int(1, 0)).conjugate * a * Int( ((a.x-1)^^2 + a.y^^2 * 5).inv, F(0) ); } void main() { auto seq = readln.split; auto a = Int(F(seq[0].to!long), F(seq[1].to!long)); auto N = seq[2].to!ulong; auto ans = solve(a, N); writeln(ans.x.n, " ", ans.y.n); } /********************************************* *********************************************/ // the struct of finite fields with p elements // p must be a prime number struct FiniteField(long p) if (p > 1) { ulong n; this(long n) { if (n < 0) this.n = n%p + p; else this.n = n%p; } FiniteField!p opUnary(string op: "+")() { return this; } FiniteField!p opUnary(string op: "-")() { return FiniteField!p(-n); } FiniteField!p opBinary(string op)(long rhs) { static if (op == "^^") { if (rhs < 0) { return this.inv() ^^ rhs; } auto result = FiniteField!p(1); auto i = 0, pow_2_i = this; // pow_2_i = n^{2^i} rhs %= (p-1); while (rhs > 0) { if (rhs % 2 == 1) { result = result * pow_2_i; } rhs >>= 1; i++; pow_2_i = pow_2_i * pow_2_i; } return result; } else { return this.opBinary!op(FiniteField!p(rhs)); } } FiniteField!p opBinary(string op)(FiniteField!p rhs) { auto result = this; static if (op == "+") { result.n = (result.n + rhs.n) % p; } else if (op == "-") { result.n = (result.n - rhs.n + p) % p; } else if (op == "*") { result.n = (result.n * rhs.n) % p; } else if (op == "/") { assert (rhs.n != 0); result.n = (result.n * rhs.inv().n) % p; } else assert(0); return result; } FiniteField!p opOpAssign(string op)(long rhs) { return this = this.opBinary!op(rhs); } FiniteField!p opOpAssign(string op)(FiniteField!p rhs) { return this = this.opBinary!op(rhs); } FiniteField!p inv() { assert (this.n != 0); return this ^^ (p-2); } string toString() { import std.conv: to; return n.to!string; } }