CFR 803 C. Maximal GCD ( Greedy )
題意:
給 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 ] )