問題
http://community.topcoder.com/stat?c=problem_statement&pm=8589&rd=11124
解き方
そのままの整数でシミュレーションすると計算量が間に合わないが
MODにして計算してあげるとシンプルになる。
MOD後の数を保存しておき、すでに現れたMOD後の数が現れると
ループしているので−１となる。
コード
class ConcatenateNumber {
public: int getSmallest(int number, int k) {
long long p=1,tmp=number;
while(tmp>0){
tmp/=10;
p*=10;
}
p%=k;
set<int> s;
int cnt=1,cur=number%k,add=number%k;
while(s.find(cur)==s.end()){
if(cur==0)return cnt;
s.insert(cur);
add=(p*add)%k;
cur=(cur+add)%k;
cnt++;
}
return -1;
}
};
public: int getSmallest(int number, int k) {
long long p=1,tmp=number;
while(tmp>0){
tmp/=10;
p*=10;
}
p%=k;
set<int> s;
int cnt=1,cur=number%k,add=number%k;
while(s.find(cur)==s.end()){
if(cur==0)return cnt;
s.insert(cur);
add=(p*add)%k;
cur=(cur+add)%k;
cnt++;
}
return -1;
}
};