Problem:


MathJax.Hub.Config({
tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}
});

B: イカったー / SNS

問題文

AOR イカちゃんは最近少し機嫌が悪い。
どうやら、”イカったー”のフォロー数とフォロワー数の比が気に入らないようだ
。現在、AOR イカちゃんのフォロー数は $A$ 人、フォロワー数は $B$ 人であり、比は $A:B$ である。

そこで、AOR イカちゃんはフォロー数とフォロワー数の比が気に入った整数比になるように、フォロー数を増減させることにした。
なお気に入った整数比とは、比に含まれるどちらの値も $1$ 以上 $N$ 以下の整数となるように表せる比である。

しかし、AOR イカちゃんはできるだけフォロー数を変更したくないので、変更前との差の絶対値をできるだけ小さくしたい。
AOR イカちゃんの機嫌を良くするために、少なくともフォロー数をいくつ変更する必要があるかを求めるプログラムを作成せよ。

入力

$A \ B \ N$

入力の制約

$1 \le A, \ B \le 10^{12}$

$1 \leq N \leq 100 $

出力

気に入った整数比にできる、$A$ の変化量の絶対値の最小値を出力せよ。

サンプル

サンプル入力1

19 30 3

サンプル出力1

1

サンプル入力2

3 7 7

サンプル出力2

0

サンプル入力3

3 7 1

サンプル出力3

4

サンプル入力4

102 30 3

サンプル出力4

12

フォローを $12$ 人減らすことで $90:30 \ (=3:1)$ になり、比の大きい方の数字が $3$ 以下となります。

このとき、変化量は $12$ です。

サンプル入力5

3 4 2

サンプル出力5

1

一人フォローを外すと $2:4 \ (=1:2)$ に、フォローすると $4:4 \ (=1:1)$ になり、どちらも増減の絶対値は $1$ でそれが答えです。

サンプル入力6

1 100 2

サンプル出力6

49

最低でも $1$ 人はフォローしていなければいけない事に注意してください。



Sample input:
19 30 3


Sample output:
1

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

INF = 2 ** 63 - 1


def solve(a, b, n):
    # a + x = k * d, b = l * g
    # 1 <= k <= n, 1 <= l <= n
    x = INF
    for l in range(1, n + 1):
        d, m = divmod(b, l)
        if not m:
            for k in range(1, n + 1):
                x = min(x, abs(k * d - a))
    return x


def main():
    a, b, n = map(int, input().split())
    print(solve(a, b, n))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
a, b, n = map(int, input().split())
score = abs(a - b)
for x in range(1, n + 1):
  for y in range(1, n + 1):
    if b * x % y == 0:
      new_a = b * x // y
      score = min(score, abs(a - new_a))
print(score)