naoya_t@topcoder

SRM234 Div1 Easy: FractionSplit

過去問, 練習 | 01:41 |

• 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;
  }
};