結果

問題 No.377 背景パターン
コンテスト
ユーザー 37zigen
提出日時 2016-06-07 14:36:04
言語 Java
(openjdk 23)
結果
WA  
実行時間 -
コード長 5,635 bytes
コンパイル時間 2,979 ms
コンパイル使用メモリ 81,664 KB
実行使用メモリ 47,368 KB
最終ジャッジ日時 2024-10-08 17:18:08
合計ジャッジ時間 13,961 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 11 WA * 3
権限があれば一括ダウンロードができます

ソースコード

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();
		// for(int i=1;i<100000;i++){
		// new Q377().test(i,i,1);
		// }
	}

	final long MOD = 1_000_000_000 + 7;

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

		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);

	}

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

		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, long k, Prime p, long h, long w) {
		return totient_function(p.primeFactorF(x), x) % MOD * totient_function(p.primeFactorF(y), y) % MOD
				* pow(k, (h * w) / ((x * y) / gcd(x, y))) % 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