Subscribed unsubscribe Subscribe Subscribe

0w1

CFR 803 C. Maximal GCD ( Greedy )

Problem - C - Codeforces

題意:
給 n, k,要求構造一個數列,數列長度必須是 k,元素總和必須是 n,而且要是嚴格遞增的。在此前提下,數列的 gcd 要最大。若不存在解則輸出 -1。

制約:
The first line consists of two numbers n and k (1 ≤ n, k ≤ 1e10).

解法:
枚舉 n 的所有因數作為可能的 gcd。顯然如果 ( 1 + 2 + 3 .. + k ) * gcd ≤ n 就是可以的,否則不行。多的往最後一個元素添就可以。

時間 / 空間複雜度:
O( N ** 0.5 ) / O( 1 )

N, K = map( int, input().split() )
if K * ( K + 1 ) // 2 > N:
  exit( print( -1 ) )
ans = 1
for i in range( 1, int( N ** 0.5 ) + 1 ):
  if N % i: continue
  if ans < i:
    if K * ( K + 1 ) // 2 <= N // i:
      ans = i
  if ans < N // i:
    if K * ( K + 1 ) // 2 <= i:
      ans = N // i
t = N // ans
for i in range( 1, K + 1 ):
  print( i * ans if i < K else N - ( K - 1 ) * K // 2 * ans, end = " \n"[ i == K ] )