#225458 (Java21) No.613 Solitude by the window

• 問題: No.613 Solitude by the window
• ユーザー: 37zigen
• 提出日時: 2017-12-22 01:35:30
• 言語: Java21 (openjdk 21)
• 結果: AC
• 実行時間: 127 ms / 2,000 ms
• コード長: 1,265 bytes
• コンパイル時間: 3,454 ms
• コンパイル使用メモリ: 73,860 KB
• 実行使用メモリ: 56,216 KB
• 最終ジャッジ日時: 2023-08-22 11:29:08
• 合計ジャッジ時間: 7,945 ms
• ジャッジサーバーID （参考情報）: judge15 / judge13

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	124 ms; 56,008 KB
testcase_01	AC	124 ms; 56,124 KB
testcase_02	AC	124 ms; 56,216 KB
testcase_03	AC	124 ms; 55,624 KB
testcase_04	AC	124 ms; 55,716 KB
testcase_05	AC	123 ms; 55,636 KB
testcase_06	AC	123 ms; 55,688 KB
testcase_07	AC	123 ms; 55,900 KB
testcase_08	AC	123 ms; 55,796 KB
testcase_09	AC	126 ms; 55,888 KB
testcase_10	AC	122 ms; 55,716 KB
testcase_11	AC	124 ms; 55,932 KB
testcase_12	AC	125 ms; 55,984 KB
testcase_13	AC	126 ms; 55,916 KB
testcase_14	AC	124 ms; 55,888 KB
testcase_15	AC	127 ms; 55,868 KB
testcase_16	AC	126 ms; 56,140 KB
testcase_17	AC	125 ms; 55,644 KB
testcase_18	AC	126 ms; 55,748 KB
testcase_19	AC	126 ms; 55,476 KB
testcase_20	AC	124 ms; 55,696 KB
testcase_21	AC	124 ms; 56,028 KB
testcase_22	AC	125 ms; 55,844 KB
testcase_23	AC	125 ms; 55,464 KB

ソースコード

import java.util.Arrays;
import java.util.Scanner;

class Main {
	long N;
	long M;

	class S {
		long a, b;

		public S(long a_, long b_) {
			a = a_ % M;
			b = b_ % M;
		}

		S mul(S s) {
			return new S(a * s.a % M + 3 * b % M * s.b % M, a * s.b % M + b * s.a % M);
		}

		S add(S s) {
			return new S(a + s.a, b + s.b);
		}

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

	void run() {
		Scanner sc = new Scanner(System.in);
		N = sc.nextLong();
		M = sc.nextLong();
		S s1 = new S(2, 1);
		S s2 = new S(2, -1);
		S ret;
		if (f(3) == 1) {
			ret = s1.pow(pow(2, N, M - 1)).add(s2.pow(pow(2, N, M - 1)));
		} else {
			ret = s1.pow(pow(2, N, M + 1)).add(s2.pow(pow(2, N, M + 1)));
		}
		System.out.println((ret.a - 2 + M) % M);

	}

	long f(long a) {
		return pow(a, (M - 1) / 2, M);
	}

	long pow(long a, long n, long mod) {
		long ret = 1;
		for (; n > 0; n >>= 1, a = a * a % mod) {
			if (n % 2 == 1) {
				ret = ret * a % mod;
			}
		}
		return ret;
	}

	void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}

	public static void main(String[] args) {
		new Main().run();
	}

}