結果

問題 No.377 背景パターン
ユーザー 37zigen37zigen
提出日時 2016-06-07 01:44:26
言語 Java21
(openjdk 21)
結果
WA  
実行時間 -
コード長 5,041 bytes
コンパイル時間 3,232 ms
コンパイル使用メモリ 81,696 KB
実行使用メモリ 47,376 KB
最終ジャッジ日時 2024-10-08 17:01:14
合計ジャッジ時間 13,155 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 AC 130 ms
41,184 KB
testcase_05 AC 116 ms
40,884 KB
testcase_06 AC 128 ms
40,912 KB
testcase_07 AC 152 ms
41,124 KB
testcase_08 AC 137 ms
40,880 KB
testcase_09 AC 134 ms
41,156 KB
testcase_10 AC 133 ms
41,328 KB
testcase_11 AC 134 ms
41,192 KB
testcase_12 AC 135 ms
41,116 KB
testcase_13 WA -
testcase_14 WA -
testcase_15 AC 131 ms
41,256 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

package yukicoder;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

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

	final int MOD = 1_000_000_000 + 7;

	void solve() {
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
		int W = sc.nextInt();
		int K = sc.nextInt();

		Prime p = new Prime((int) Math.sqrt(1_000_000_000));
		ArrayList<Factor> fh = p.primeFactorF(H);
		ArrayList<Factor> fw = p.primeFactorF(W);
		long sum = 0;
		ArrayList<Long> dh = enum_div(fh);
		ArrayList<Long> dw = enum_div(fw);
		for (int i = 0; i < dh.size(); i++) {
			for (int j = 0; j < dw.size(); j++) {
				sum += f(dh.get(i), dw.get(j), K, p, H, W);
				sum = sum % MOD;
			}
		}
		System.out.println(sum * inv(W * H, MOD) % MOD);
	}

	long inv(long a, long mod) {
		long b = mod;
		long p = 1, q = 0;
		while (b > 0) {
			long c = a / b;
			long d;
			d = a;
			a = b;
			b = d % b;
			d = p;
			p = q;
			q = d - c * q;
		}
		return p < 0 ? p + mod : p;
	}

	// nの約数を列挙
	// 1とnを含む。
	ArrayList<Long> enum_div(ArrayList<Factor> f) {
		ArrayList<Long> ret = new ArrayList<Long>();
		ret.add(1L);
		for (int i = 0; i < f.size(); i++) {
			long a = 1;
			int n = ret.size();
			for (int j = 0; j < f.get(i).exp; j++) {
				a *= f.get(i).base;
				for (int k = 0; k < n; k++) {
					ret.add(ret.get(k) * a);
				}
			}
		}
		return ret;
	}

	long f(long x, long y, int k, Prime p, int h, int w) {
		return totient_function(p.primeFactorF(x), x) % MOD * totient_function(p.primeFactorF(y), y) % MOD
				* pow(k, (h * w)/(x*y)% MOD * gcd(x, y) % MOD ) % MOD;
	}

	class Prime {
		long n;
		ArrayList<Integer> ps = new ArrayList<Integer>();

		Prime(long n) {
			this.n = n;
			ps = primeList((int) Math.sqrt(n));
		}

		boolean[] isPrimeArray(int max) {
			boolean[] isPrime = new boolean[max + 1];
			Arrays.fill(isPrime, true);
			isPrime[0] = isPrime[1] = false;
			for (int i = 2; i * i <= max; i++) {
				if (isPrime[i]) {
					for (int j = 2; j * i <= max; j++) {
						isPrime[j * i] = false;
					}
				}
			}
			return isPrime;
		}

		/*
		 * max以下の素数のリストを返す
		 */
		ArrayList<Integer> primeList(int max) {
			boolean[] isPrime = isPrimeArray(max);
			ArrayList<Integer> primeList = new ArrayList<Integer>();
			for (int i = 2; i <= max; i++) {
				if (isPrime[i]) {
					primeList.add(i);
				}
			}
			return primeList;
		}

		/*
		 * numをprimeListの素数をもとに素因数分解し、因数を ArrayList<Factor>の形で返す。1は含まれない。
		 * primeListにはnumの平方根以下の素数が含まれていなければならない。
		 *
		 */
		ArrayList<Factor> primeFactorF(ArrayList<Integer> primeList, long num) {
			ArrayList<Factor> ret = new ArrayList<Factor>();
			for (int p : primeList) {
				int exp = 0;
				while (num % p == 0) {
					num /= p;
					exp++;
				}
				if (exp > 0)
					ret.add(new Factor(p, exp));
			}
			if (num > 1)
				ret.add(new Factor(num, 1));
			return ret;
		}

		ArrayList<Factor> primeFactorF(long num) {
			ArrayList<Factor> ret = new ArrayList<Factor>();
			for (int p : ps) {
				int exp = 0;
				while (num % p == 0) {
					num /= p;
					exp++;
				}
				if (exp > 0)
					ret.add(new Factor(p, exp));
			}
			if (num > 1)
				ret.add(new Factor(num, 1));
			return ret;
		}
	}

	class Factor {
		long base, exp;

		Factor(long base, long exp) {
			this.base = base;
			this.exp = exp;
		}
	}

	/*
	 * 戻り値：約数の和 verified:yukicoder No.278
	 */
	long sum_d(ArrayList<Factor> fs) {
		long sum = 1;
		for (Factor f : fs) {
			sum *= Long.parseLong((BigInteger.ONE.subtract(pow_big(f.base, f.exp + 1)))
					.divide(BigInteger.ONE.subtract(BigInteger.valueOf(f.base))).toString());
		}
		return sum;
	}

	BigInteger pow_big(long a, long n) {
		BigInteger A = new BigInteger(String.valueOf(a));
		BigInteger ans = BigInteger.ONE;
		while (n >= 1) {
			if (n % 2 == 0) {
				A = A.multiply(A);
				n /= 2;
			} else if (n % 2 == 1) {
				ans = ans.multiply(A);
				n--;
			}
		}
		return ans;
	}
	/*
	 * Eulerのφ関数(Euler's totient function) 1からnまでの自然数のうちnと互いに素なものの個数を数える。
	 * φ(mn)=φ(m)φ(n) (gcd(m,n)=1) なぜならば、chinese reminder theoremより、 a mod mnと
	 * (a mod n)と(b mod m)は全単射。 φ(p^k)=p^k-p^(k-1)=p^k(1-1/p)
	 * よってφ(p^k*q^k)=n(1-1/p)(1-1/q)という風にできる。
	 */

	long totient_function(ArrayList<Factor> f, long n) {
		long ret = n;
		for (int i = 0; i < f.size(); i++) {
			ret = ret - ret / f.get(i).base;
		}
		return ret;
	}

	long gcd(long t1, long t2) {
		if (t1 < t2) {
			long d = t2;
			t2 = t1;
			t1 = d;
		}
		if (t2 == 0)
			return t1;
		return gcd(t2, t1 % t2);
	}

	long pow(long a, long n) {
		long A = a;
		long ans = 1;
		while (n >= 1) {
			if (n % 2 == 0) {
				A = (A * A) % MOD;
				n /= 2;
			} else if (n % 2 == 1) {
				ans = (ans * A) % MOD;
				n--;
			}
		}
		return ans;
	}
}
0