結果

問題 No.377 背景パターン
コンテスト
ユーザー 37zigen
提出日時 2016-06-07 19:51:03
言語 Java
(openjdk 23)
結果
AC  
実行時間 916 ms / 5,000 ms
コード長 5,533 bytes
コンパイル時間 2,783 ms
コンパイル使用メモリ 81,512 KB
実行使用メモリ 42,936 KB
最終ジャッジ日時 2024-10-08 18:09:00
合計ジャッジ時間 8,025 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

package yukicoder;

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 long MOD = 1_000_000_000 + 7;

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

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

		long[] totient_h=new long[dh.size()];
		long[] totient_w=new long[dw.size()];
		for(int i=0;i<dh.size();i++){
			totient_h[i]=totient_function(p.primeFactorF(dh.get(i)),dh.get(i));
		}
		for(int i=0;i<dw.size();i++){
			totient_w[i]=totient_function(p.primeFactorF(dw.get(i)),dw.get(i));
		}
		for (int i = 0; i < dh.size(); i++) {
			for (int j = 0; j < dw.size(); j++) {
				sum+=totient_h[i] % MOD * totient_w[j] % MOD
				* pow(K, (H * W) / ((dh.get(i) * dw.get(j)) / gcd(dh.get(i), dw.get(j)))) % MOD;
				sum = sum % MOD;
			}
		}
		System.out.println(sum * inv(W * H, MOD) % MOD);
	}
//	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;
//	}

	// aとmodは互いに素
	/*
	 * ax+my=1となるx,yを見つける。 1*m+0*a=m 0*m+1*a=a から 1*m-1*a*(m/a)=m%a として
	 * 1*m-1*a*(m/a)=m%a 0*m+1*a=a で同様に考える。一般化すると x*m+y*a=s z*m+w*a=t (s>t)だとすると
	 *
	 * (x-s/t*z)*m+(y-s/t*w)*a=s%t を生み出す。 続けると ?*m+??*a=1が得られる。
	 * ??が求めたいxである。ただし、x<0の可能性があるので、mの剰余系でプラスにする。 mの係数はどうでもいいことに注意する
	 */
	long inv(long a, long mod) {
		if (gcd(a, mod) != 1)
			throw new ArithmeticException("ax=1 mod mはgcd(a,x)!=1のとき解なし");
		a = a % mod;
		long b = mod;
		long p = 1, q = 0;
		// ? + qa = b
		// ? + pa = a (b>a)

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

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

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

		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>();
			long p = primeList.get(0);
			for (int i = 0; p * p <= n; i++, p = primeList.get(i)) {
				long 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 (long 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;
		}
	}

	/*
	 * 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