PKU 2897 Dramatic Multiplications

http://poj.org/problem?id=2897
整数n,kが与えられる。(1<=n,k<=9)
この時、1の位がkでn倍したときの結果が元の数字の各桁を右に一つシフトしたものになる数字のうち最小のものを求めろというような問題。

多倍長が必要だったので、pythonに計算させて埋め込みしました。

import sys,random

print '{',
for i in range(9):
    print'{',
    for k in range(9):
        d10=1
        ans=-1
        for d in range(1000):
            n=i
            x=(k+1)*(d10-n-1)/(10*n+9)
            if x*(10*n+9)==(k+1)*(d10-n-1) and x<d10 and d10/10<=x:
                ans=x
                break
            d10=d10*10
        if ans==-1:
            ans=0
        else:
            ans=ans*10+k+1
        print '"'+str(ans)+'",',
    print '},'
print '}'

サブミットしたもの

string out[][9]={ { "1", "2", "3", "4", "5", "6", "7", "8", "9", },
{ "0", "105263157894736842", "157894736842105263", "210526315789473684", "263157894736842105", "315789473684210526", "368421052631578947", "421052631578947368", "473684210526315789", },
{ "0", "0", "1034482758620689655172413793", "1379310344827586206896551724", "1724137931034482758620689655", "2068965517241379310344827586", "2413793103448275862068965517", "2758620689655172413793103448", "3103448275862068965517241379", },
{ "0", "0", "0", "102564", "128205", "153846", "179487", "205128", "230769", },
{ "0", "0", "0", "0", "102040816326530612244897959183673469387755", "122448979591836734693877551020408163265306", "142857", "163265306122448979591836734693877551020408", "183673469387755102040816326530612244897959", },
{ "0", "0", "0", "0", "0", "1016949152542372881355932203389830508474576271186440677966", "1186440677966101694915254237288135593220338983050847457627", "1355932203389830508474576271186440677966101694915254237288", "1525423728813559322033898305084745762711864406779661016949", },
{ "0", "0", "0", "0", "0", "0", "1014492753623188405797", "1159420289855072463768", "1304347826086956521739", },
{ "0", "0", "0", "0", "0", "0", "0", "1012658227848", "1139240506329", },
{ "0", "0", "0", "0", "0", "0", "0", "0", "10112359550561797752808988764044943820224719", },
                    };


main(){
  int T;
  cin>>T;
  while(T--){
    int n,k;
    cin>>n>>k;
    cout<<out[n-1][k-1]<<endl;
  }
}