AtCoder Regular Contest #004 C: 平均値太郎の憂鬱

問題

以下を参照のこと。
https://beta.atcoder.jp/contests/arc004/tasks/arc004_3

方針

これは数学よりの問題だと思います。上手く式変形できることと、割り算に気をつけることがポイントと感じました。
問題文より以下の式が成り立ちます。

\dfrac{\dfrac{n(n+1)}{2} - m}{n} = \dfrac{x}{y}

これは適当に式を変形させると以下のようにできます。(式の記述に不備がありました。isyumi-net さんありがとうございます！)
\Leftrightarrow n=2(\dfrac{x}{y}+\dfrac{m}{n}) - 1 ,m=(\dfrac{n(n+1)}{2} - \dfrac{nx}{y})

仮定より、 m, n は整数で変域は 1 \leq m \leq n でしたから、両辺を n で割って、

\Leftrightarrow \dfrac{1}{n} \leq \dfrac{m}{n} \leq 1

\Leftrightarrow 2(\dfrac{1}{n}+\dfrac{x}{y})-1 \leq 2(\dfrac{m}{n}+\dfrac{x}{y})-1 \leq 2(1+\dfrac{x}{y})-1

ということから n は \dfrac{2x}{y} \leq n \leq \dfrac{2x}{y}+1 の整数であることが分かります。
つまり n = \dfrac{2x}{y} または n = \dfrac{2x}{y}+1 のどちらかの整数です。
その時の m は m = \dfrac{n(n+1)}{2} - \dfrac{nx}{y} で与えられます。

これで (m, n) は容易に求まるようになりました。

実装上の注意点

・x < y となっている場合は、必ず不可能なので、returnする。
・ m が整数になるためには n が y で割り切れる必要がある。
・Inputの x,y は既約分数ではない可能性があるので、最大公約数で割って既約分数にする必要がある。

といったところでしょうか。

import java.util.Scanner;
public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        String[] s = in.next().split("/");
        long x = Long.parseLong(s[0]);
        long y = Long.parseLong(s[1]);

        long g = gcd(x, y);
        x /= g;
        y /= g;

        boolean isFound = false;

        if (x < y) {
            System.out.println("Impossible");
            return;
        }

        for (int i = 0; i < 2; i++) {
            long n = 2*x/y+i;
            if (n % y == 0) {
                long m = n*(n+1)/2-n/y*x;
                if (1 <= m && m <= n) {
                    System.out.println(n +" "+ m);
                    isFound = true;
                }
            }
        }

        if (!isFound) {
            System.out.println("Impossible");
        }
    }

    public static long gcd(long a, long b) {
        return (b == 0) ? a : gcd(b, a % b);
    }

}