結果
問題 | No.1658 Product / Sum |
ユーザー | 👑 SPD_9X2 |
提出日時 | 2021-08-27 22:15:37 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 92 ms / 2,000 ms |
コード長 | 1,229 bytes |
コンパイル時間 | 432 ms |
コンパイル使用メモリ | 86,716 KB |
実行使用メモリ | 79,952 KB |
最終ジャッジ日時 | 2023-08-13 09:17:35 |
合計ジャッジ時間 | 4,061 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 73 ms
71,304 KB |
testcase_01 | AC | 72 ms
71,164 KB |
testcase_02 | AC | 72 ms
71,236 KB |
testcase_03 | AC | 72 ms
71,424 KB |
testcase_04 | AC | 71 ms
71,104 KB |
testcase_05 | AC | 92 ms
79,848 KB |
testcase_06 | AC | 92 ms
79,952 KB |
testcase_07 | AC | 81 ms
76,508 KB |
testcase_08 | AC | 90 ms
79,260 KB |
testcase_09 | AC | 82 ms
77,160 KB |
testcase_10 | AC | 81 ms
77,044 KB |
testcase_11 | AC | 81 ms
76,428 KB |
testcase_12 | AC | 80 ms
76,736 KB |
testcase_13 | AC | 81 ms
77,288 KB |
testcase_14 | AC | 92 ms
79,792 KB |
testcase_15 | AC | 83 ms
77,460 KB |
ソースコード
""" 積/和が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)