結果
問題 | No.1658 Product / Sum |
ユーザー |
![]() |
提出日時 | 2021-08-27 22:15:37 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 60 ms / 2,000 ms |
コード長 | 1,229 bytes |
コンパイル時間 | 149 ms |
コンパイル使用メモリ | 82,236 KB |
実行使用メモリ | 79,140 KB |
最終ジャッジ日時 | 2024-11-21 02:59:30 |
合計ジャッジ時間 | 2,403 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 |
ソースコード
""" 積/和がK a*b / a+b = K a*b*c*... = (a+b+c+...) * K a a = xKにしてみる xK*b = K(xK+b) xb = xK + b b(x-1) = xK b = xK / (x-1) 和をSとしてみる S をN分割、積がSKになるようにする NK / N = K Kが素数の場合を考えよう K,1,1,1,1,1... に加えていく。 この時積はK,和は N+K-1 である。 まだ和の方が大きい。 K * a == N+K-1 + a-1 となる aが居れば、2項目をaにするだけでok aK = N+K+a-2 a(K-1) = N+K-2 a = (N+K-2)/(K-1) これは整数とは限らないな… K := xK (xは好きな数字) でも同じことができる。 (N+xK-2) / (xK-1) が整数となるようなxを見付ければよい。 (N+xK-2) == 0 mod xK-1 N-1 == 0 mod xK-1 xK-1 は、N-1の約数ならおk xK,a,1,1,1,1... 積 = xKa 和 = N + (xK-1) + (a-1) xa = N + (xK-1) + (a-1) xa = N-1 + (xK-1) + a (x-1)a = (N-1) + (xK-1) a = (N+xK-2) / (x-1) xK = 30 K = 5 x = 6 x-1 = 5 N = 2 a = 6 a = K+1 ?? (x-1)(K+1) = (N-1) + (xK-1) xK - K + x -1 = N-1 + xK-1 -K+x = N-1 x = N+K-1 これを満たす、 x,aを見付けたい """ from sys import stdin N,K = map(int,stdin.readline().split()) A = [1] * N x = N+K-1 a = K+1 A[0] = x * K A[1] = a print (*A)