TopCoder SRM 657 Div1 Medium: PolynomialGCD

解法

例えばs="2014"の時、
 P(x) = (x-0)^{2} \times (x-1)^{0} \times (x-2)^1 \times (x-3)^4
となる。
素因数に2を含む個数は、x=4の時、P(4)は5個、P(5)なら4個、P(6)なら4個、P(7)なら8個、P(8)なら……と増えていくが、正の個数で最小の個数は4個であることが分かる。このように各素数ごとに素因数の最小個数を求めると、"少なくとも"いくつで割り切れるかを求めることが出来る。

コード

import java.util.Arrays;

public class PolynomialGCD {

	private final int MOD = 1000000007;

	public int gcd(String s) {
		int N = s.length();
		boolean[] isPrime = new boolean[N + 1];
		Arrays.fill(isPrime, true);
		isPrime[0] = isPrime[1] = false;
		for (int i = 2; i < isPrime.length; i++) {
			if (isPrime[i]) {
				for (int j = 2 * i; j < isPrime.length; j += i) {
					isPrime[j] = false;
				}
			}
		}

		long ans = 1;
		for (int prime = 0; prime < isPrime.length; prime++) {
			if (!isPrime[prime]) {
				continue;
			}
			ans *= pow(prime, getMinDivideTimes(s, prime));
			ans %= MOD;
		}
		return (int) ans;

	}

	long pow(long b, long e) {
		// b^e%MODを返す
		long ret = 1;
		while (e > 0) {
			if (e % 2 == 1) {
				ret *= b;
				ret %= MOD;
			}
			b = (b * b) % MOD;
			e /= 2;
		}
		return ret;
	}

	int getMinDivideTimes(String s, int prime) {
		int N = s.length();
		if (prime > N) {
			return 0;
		}

		int min = Integer.MAX_VALUE;
		for (int i = 0; i < prime; i++) {
			// i文字目からスタートした時にsの中のprimeの倍数番目にある素因数の数
			/*
			 * x=iとした時にP(x)をprimeで何回割れるかを返す
			 */
			int sum = 0;
			StringBuilder sb = new StringBuilder();
			for (int j = i; j < N; j += prime) {
				sum += (s.charAt(j) - '0');
				sb.append(s.charAt(j));
			}
			sum += getMinDivideTimes(sb.toString(), prime);
			min = Math.min(min, sum);
		}
		return min;
	}
}