読者です 読者をやめる 読者になる 読者になる

UVa10976 Fractions Again?!

問題
http://uva.onlinejudge.org/external/109/10976.html

制約
入力は 10000 以下。

解法
数学の問題。
定数 K が入力で定まるので、x か y を動かせばもう片方の変数が特定できる。
ポイントは入力から変数の制約(未知情報の制約)を見つけること。変数の最大は 10000 ではなく、K*2 <= 20000 となる。

#include <iostream>
#include <sstream>
 
#define REP(i, a, b) for(int i=(a);i<(b);i++)
 
using namespace std;
 
int main() {
  int K;
  while(cin >> K) {
    // x*y == K*(x+y)
    stringstream ss;
    int cnt = 0;
    REP(y, 1, K*2+1) {
      if(y == K) continue;
      int x = K*y / (y-K);
      if(x < 1) continue;
      if(x < y) continue;
      if(x*y == K*(x+y)) {
        ss << "1/" << K << " = 1/" << x << " + 1/" << y << endl;
        cnt++;
      }
    }
    cout << cnt << endl;
    cout << ss.str();
  }
  return 0;
}