結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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;
    }
}
0