Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-05-23

SRM234 Div1 Easy: FractionSplit

| 01:41 | SRM234 Div1 Easy: FractionSplit - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM234 Div1 Easy: FractionSplit - naoya_t@topcoder SRM234 Div1 Easy: FractionSplit - naoya_t@topcoder のブックマークコメント

  • gcd()は自前
  • 232.51points (7'54''), Passed system test
  • intで足りるのかとか心配したけど大丈夫だったようだ
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;
  }
}

class FractionSplit {
 public:
  vector<string> getSum(int n, int d) {
    vs ans;
    for(int x=2;n>0;x++){
      // n/d >= 1/x : nx >= d
      int nr = n*x - d;
      if (nr >= 0){
        // n/d - 1/x = (nx-d)/xd
        char buf[128];
        sprintf(buf,"1/%d",x);
        ans.pb(buf);
        if(nr==0) break;
        int dr = x*d;
        int g = gcd(nr,dr);
        n = nr / g; d = dr / g;
      }
    }
    return ans;
  }
};
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20090523