naoya_t@topcoder

SRM390 Div1 Easy: ConcatenateNumber

過去問, 練習 | 09:57 |

余裕・・・と思ってたら循環するのを忘れててシステムテストエラー

class ConcatenateNumber {
public:
  int getSmallest(int number, int k) {
    long long f=1, k_=k;
    for(int n=number;n>0;n/=10) f*=10;
    f%=k;
    long long n_=number%k, rem=n_;
    if(rem==0) return 1;

    set<int> rep; rep.insert(rem); // 循環検出用。bool[k]でいいんですけど

    int cnt=1;
    while(1){
      cnt++;
      long long new_rem = ((rem*f) + n_)%k_;

      if(found(rep,new_rem)) return -1;
      // if(new_rem==rem) return -1; // これだけだと駄目

      if(new_rem==0) return cnt;
      rep.insert(new_rem);
      rem=new_rem;
    }
  }
};