Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-01-09

SRM375 Div1 Easy: DivisibleByDigits

| 12:22 | SRM375 Div1 Easy: DivisibleByDigits - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM375 Div1 Easy: DivisibleByDigits - naoya_t@topcoder SRM375 Div1 Easy: DivisibleByDigits - naoya_t@topcoder のブックマークコメント

  • long longとか打ってるのが馬鹿馬鹿しい。typedef long long ll; は常備しないと。
  • #define ... の行とか消しとかないと30% unused codeルールに引っかかって、消してまたsubmitとか時間のロス
  • 7'40''
int gcd(int m, int n)
{
  if (m == 0 || n == 0) return 0;
  if (m == 1 || n == 1) return 1;
  if (m == n) return m;
  while (1) {
        if (m == 0) return n;
        if (n == 0) return m;
        if (m > n) m %= n; else n %= m;
  }
}
int lcm(int m, int n)
{
  return m / gcd(m,n) * n;
}

class DivisibleByDigits {
 public:
  long long getContinuation(int n) {
    long long de=1LL;
    for(int _=n;_>0;_/=10){
      int r=_%10;
      if(r) de=lcm(de,r);
    }
    for(long long b=n,m=1;b<=LONG_LONG_MAX;b*=10,m*=10){
      long long r=b%de;
      if(r==0)return b;
      long long s=de-r;
      if(s<=m-1)return b+s;
    }
    return 0;
  }
};
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20090109