鏈接一
鏈接二
You are given positive integer number n. You should create such strictly increasing sequence of k positive numbers a1,?a2,?…,?ak, that their sum is equal to n and greatest common divisor is maximal.

Greatest common divisor of sequence is maximum of such numbers that every element of sequence is divisible by them.

If there is no possible sequence then output -1.

Input

The first line consists of two numbers n and k (1?≤?n,?k?≤?1010).

Output

If the answer exists then output k numbers — resulting sequence. Otherwise output -1. If there are multiple answers, print any of them.

Examples

Input

6 3

Output

1 2 3

Input

8 2

Output

2 6

Input

5 3

Output

-1

思路

題目轉換：
N >= gcd * (1 + 2 + ….+ k)
N在符合上面的式子下求最大的gcd。
可以從1開始枚舉gcd 直到剛好大于或等于N的時候停止，最后貪心輸出答案

注意細節

求（1 + 2 + … + k）的時候可能會爆 long long

可以用sqrt枚舉，降低復雜度

AC

#include<bits/stdc++.h> #define N 10006 #define ll long long using namespace std; ll n, k, limit; int judge(ll x) { //判斷此時的gcd是否合適 if(limit <= x) return 1;else return 0; } int main() { // freopen("in.txt", "r", stdin);while (scanf("%lld%lld", &n, &k) != EOF) {limit = (1 + k) * k / 2; if (k > 141421 || limit > n){ //特判不符合條件，limit 也可能爆long longprintf("-1\n");continue;} if (limit == n) { //特判相等 答案：1--k for (ll i = 1; i <= k; i++) printf("%d ", i);printf("\n");}else {ll gcd;for (ll i = 1; i <= sqrt(n); i++) { //每次找n的因子，sqrt降低復雜度，否則1e10 if (n % i == 0) {if (judge(i)) { //此時使得 gcd = n / i 最大，即為答案 gcd = n / i;break;}if (judge(n / i)) { //gcd從小找，找到不合適的就退出 gcd = i;}else {break;}}//同理也可以寫成 // if (n % i == 0) { // if (i >= limit) { // gcd = n / i; // break; // }; // if(n / i >= limit) { // gcd = i; // } // } }//貪心輸出答案，前K - 1項為 1*gcd到k-1*gcd ll temp = n / gcd;for(ll i = 1; i < k; i++) { //輸出前K項 printf("%lld ", gcd * i);temp -= i;}printf("%lld\n", gcd * temp); //輸出最后一項}} return 0; }

總結

以上是生活随笔為你收集整理的CodeForces - 803C Maximal GCD（贪心 + 枚举）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。