もう5年近く前のことですが、私と同じように解いた解説が出てこないので書いてみます。
問題はこれです。
https://code.google.com/codejam/contest/1363489/dashboard#s=p1
要約すると、
a(0)=A
a(n)=a(n-1)
a(n-1)
を満たす配列anの第B項をCで割った余りで答えよ。
このA,B,Cの値の組のテストケース数は500以下
Aの値は1,000以下
Bの値はSmallは2以下、Largeは1,000以下
Cの値は1,000以下
公開鍵暗号の原理と同じで周期から計算できるんだろーなとは思ったんですが、やはりGoogleの解説もそのようになっています。
https://code.google.com/codejam/contest/1363489/dashboard#s=a&a=1
このCode Jam Japanの決勝問題は問題Aが簡単、それに比べて問題B以降が難しく、終了時点で問題AのSmall, Largeだけ解けた人が112位から355位まで大渋滞しています。
https://code.google.com/codejam/contest/1363489/scoreboard#sp=91
200位以内に入れば景品の
Tシャツがもらえるんですが、問題Aを解いただけでは早く解いた者勝ちです。そこに入れない場合は、どの問題でもいいからSmallだけでも解ければTシャツ圏内に入れる、という状況でした。
で、この問題BのSmallはBが2以下なので、 第2項まで求めればいいようになっています。つまり
(AA)(AA)までのmodが計算できれば解けることになります。
X = A
A mod C
として、
X
(AA)
を求めるわけですが、当然指数のA
Aはmodは効かずこれ自体が天文学的数字になる可能性があります。どうにかXの方をmodしながらべき乗していって求める方法を考えないとダメそうです。
で、苦し紛れに
(X
A)
A
で同じにならないかな？と思ってもこれは
X
(A*A) = X
(A2)
にしかなりません。
掛け算で並べて書けばわかりやすいんですが、例えばAが5とするとXの5乗は
X*X*X*X*X
これのさらに5乗は縦に書き足せば
X*X*X*X*X*
X*X*X*X*X*
X*X*X*X*X*
X*X*X*X*X*
X*X*X*X*X
Xが5*5個なので
X
(5*5) = X
(52)
にしかなりません。
しかし、これをさらに5乗すれば
X
(5*5*5) = X
(53)
になります。
ということは、この調子でXを5乗する、を5回繰り返せば
X
(5*5*5*5*5) = X
(55)
が求まることになります。同様に、
X(AA)を求めるためには、XをA乗するのをA回繰り返せばよい、ということになります。
A,B,Cがjavaのintとして与えられているとして、BigIntegerクラスのmodPowを使って書けば、
BigInteger a = BigInteger.valueOf(A);
BigInteger b = BigInteger.valueOf(B);
BigInteger c = BigInteger.valueOf(C);
BigInteger X = a.modPow(a, c);
for (int i = 0; i < A; i++)
X = X.modPow(a, c);
とまあ、とても短いプログラムで求めることができます。
実際私はmodPowメソッドの存在を知らなかったのでこれ相当の関数を自分で作り、終了前15分で解答提出、260位(?)あたりから一気に89位に浮上、終了時点で96位、最終的に93位で無事Tシャツを頂きました。
BigIntegerを使ってキレイに書きなおせば以下のようなコードになります。
import java.math.BigInteger;
import java.util.Scanner;
public class B {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int i = 1; i <= T; i++) {
System.out.println("Case #" + i + ": " +
resolv(sc.nextInt(), sc.nextInt(), sc.nextInt()));
}
}
private static int resolv(int A, int B, int C) {
BigInteger a = BigInteger.valueOf(A);
BigInteger b = BigInteger.valueOf(B);
BigInteger c = BigInteger.valueOf(C);
BigInteger X = a.modPow(a, c);
if (B == 2)
for (int i = 0; i < A; i++)
X = X.modPow(a, c);
return X.intValue();
}
}
実はこのBigIntegerクラス、1,000
1,000も扱えてしまうので、上で書いたようなことは全く考える必要もなく、そのまま素直にコーディングすれば解けてしまうのでした。
import java.math.BigInteger;
import java.util.Scanner;
public class B2 {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int i = 1; i <= T; i++) {
System.out.println("Case #" + i + ": " +
resolv(sc.nextInt(), sc.nextInt(), sc.nextInt()));
}
}
private static int resolv(int A, int B, int C) {
BigInteger a = BigInteger.valueOf(A);
BigInteger b = BigInteger.valueOf(B);
BigInteger c = BigInteger.valueOf(C);
BigInteger X = a.pow(A); //
最大1,0001,000
BigInteger Xm = X.mod(c);
if (B == 2)
Xm = Xm.modPow(X, c); //
そのまま計算
return Xm.intValue();
}
}
結局ライブラリ知ってるもん勝ちな問題でした。
