TopCoder SRM 657 Div1 Medium: PolynomialGCD
解法
例えばs="2014"の時、
となる。
素因数に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; } }