$F_p(\sqrt a)$構造体

目的

$F_p(\sqrt a)$の計算をするための構造体です。下の実装では$\sqrt a=\sqrt 5$として実装しています。

使い方

long MOD
目的の項のpに相当します。
long a,long b
構造体Vに$a+\sqrt 5 b$という数をセットします。
V mul(V o)
その構造体自身とoとの積をreturnします。
V sub(V o)
その構造体自身からoを引いたものをreturnします。
V conj(V o)
その構造体自身と共役なもの、つまり$a-\sqrt 5 b$をreturnします。
V div(V o)
その構造体自身をoで割ったものをreturnします。
V pow(V n)
その構造体自身のn乗をreturnします。

ソースコード

long MOD;

class V {
	long a;
	long b;

	public V(long a_, long b_) {
		a = a_ % MOD;
		b = b_ % MOD;
	}

	V mul(V o) {
		return new V(a * o.a % MOD + 5 * b * o.b % MOD, a * o.b % MOD + o.a * b % MOD);
	}

	V add(V o) {
		return new V(a + o.a, b + o.b);
	}

	V sub(V o) {
		return new V((a - o.a + MOD) % MOD, (b - o.b + MOD) % MOD);
	}

	V conj() {
		return new V(a, (MOD - b) % MOD);
	}

	V div(V o) {
		long coe = inv((o.a * o.a % MOD - o.b * o.b % MOD * 5 % MOD + MOD) % MOD);
		V v = this.mul(o.conj());
		return new V(v.a * coe % MOD, v.b * coe % MOD);
	}

	V pow(long n) {
		V ret = new V(1, 0);
		V p = new V(a, b);
		for (; n > 0; n >>= 1, p = p.mul(p)) {
			if (n % 2 == 1) {
				ret = ret.mul(p);
			}
		}
		return ret;
	}

}