今回は、 yukicoder の問題紹介・解説を行っていきたいと思います！
2問目に紹介する問題はこちら！
概要
問題 ： No.1658 Product / Sum
レベル ： ★★
実行時間制限 ： 2000 ms
問題文へのリンク↓↓
問題文
$\displaystyle \frac{A_1 \times A_2 \times \dots \times A_n}{A_1 + A_2 + \dots + A_N} = K$ を満たす $N$ 個の正の整数 $A_1, A_2, \dots, A_N$ を $1$ 組求めてください。
本問の制約のもとで、答えは必ず存在することが証明できます。
制約
- $2 \leq N \leq 10^5$
- $1 \leq K \leq 10^5$
- 入力は全て整数
入力例
入力
2 5
出力
6 30
$\displaystyle \frac{A_1 \times A_2}{A_1 + A_2} = \frac{6 \times 30}{6 + 30} = 5$ となります。
解説
ここからは解説をしていきます。
自力で解いて見たい方はここでストップしてください！
大きい数は使えない
与式を変形すると以下のようになります。
\prod_{i=1}^{N} A_i = K \times \sum_{i=1}^{N}A_i
$K$という定数が右辺にかかっていますが、本質は和と積の等式です。
和と積では積の方が早く発散する ので、基本的に １ ばかりで埋めていくことを考える。
全て1の場合
全ての値を1にした場合ではまだ右辺の方が大きいのは明らかです。
1 = NK
となってしまうので、 $K \neq 1$ 以外で落ちてしまいます。
１つだけ1以外した場合
全て1がダメだったので、１つだけ違う値で置いてみましょう。
その値を $A_1 = x$ とします。
立式していきましょう！
\prod_{i=1}^{N} A_i = K \times \sum_{i=1}^{N}A_i \\
x = K \times \{ x + (N - 1) \} \\
x = \frac{(N - 1) K}{1 - K} \\
ここで、 $x$ を構築することができましたが、実は $K \geq 2$ でこれは負の値になってしまい、
問題文の条件を満たさなくなってしまいます。
ではもう１つ１以外の値で構築してみましょう。
2つだけを１以外にした場合
その値を $A_1 = x, A_2 = y$ とします。
立式していきましょう！
\prod_{i=1}^{N} A_i = K \times \sum_{i=1}^{N}A_i \\
xy = K \times \{ x + y + (N - 2) \} \\
(x - K)(y - K) = K(N - 2 + K) \\
両辺を因数分解することができたので、解を１つ求めてみましょう。
すると、
\left\{
\begin{array}{l}
x - K = K \\
y - K = N - 2 + K
\end{array}
\right.
\left\{
\begin{array}{l}
x = 2K \\
y = N - 2 + 2K
\end{array}
\right.
$x$ は明らかに正であることが確認できます。
$y$ の方についても不等式で評価してみましょう！
y = N - 2 + 2K \geq 2 - 2 + 2 \times 1 = 2 \geq 0
したがって、このような構築を行うことでこの問題を解くことが出来ました。
ACコード
n, k = map(int, input().split())
ans = [2 * k, n - 2 + 2 * k]
for _ in range(n - 2):
ans.append(1)
print(*ans)
最後に
最後まで読んできただきありがとうございました！
構築問題はやはり面白いですね！！
リクエストなどがあればぜひ声かけて下さい！ありがとうございました！