問題
http://community.topcoder.com/stat?c=problem_statement&pm=10635&rd=13905
ある整数が与えられ、下のように同じ数が段になって足されているとき、
そのような元の数の最小値を求める。
１２
１２
ーーー
１３２
解き方
最後の一桁を固定して、すべての元の数の桁数で全探索して・・・と
考えたくなるが、段になって足されているということは
元の数に１１、１１１、１１１１・・・のいずれかの数が
かけられたものになる。
よって、１、１１、１１１・・・と割っていき
割りきれるもののうち最小の商が答えになる。
コード
class MagicalSource {
public: long long calculate(long long x) {
long long ret=x;
long long p=1LL;
while(p<x){
p=p*10+1;
if(x%p==0)ret=min(ret,x/p);
}
return ret;
}
};
public: long long calculate(long long x) {
long long ret=x;
long long p=1LL;
while(p<x){
p=p*10+1;
if(x%p==0)ret=min(ret,x/p);
}
return ret;
}
};