Maximal GCD

最新推荐文章于 2024-06-18 19:13:21 发布

gtuif

最新推荐文章于 2024-06-18 19:13:21 发布

阅读量254

点赞数

分类专栏：数学 Codeforces

本文链接：https://blog.csdn.net/gtuif/article/details/78444833

版权

数学同时被 2 个专栏收录

45 篇文章

订阅专栏

Codeforces

19 篇文章

订阅专栏

You are given positive integer number n. You should create such strictly increasing sequence of k positive numbers a₁, a₂, ..., a_k, 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 ≤ 10¹⁰).

Output

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

Example

Input

6 3

Output

1 2 3

Input

8 2

Output

2 6

Input

5 3

Output

-1

题意：给你一个数n,让你将其划分为k个数，并且保证n和每个数的最大公约数最大，如果没有输出-1；

思路：很明显应该我们应该先从n的因子找起，看一眼数据范围是1e10,但用根号的话只有1e5,所以时间上能过，但注意根号后的因子也要记录，然后我们在一遍一遍的遍历他的因子，遍历的时候只要判断最后一个值是否符合条件就行了；

下面附上我的代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k;
ll a[200005],b[200005];
int main()
{
	while(cin>>n>>k)
	{
		int l=0; 
		if((k+1)*k/2>n||k>5e5)
		{
			puts("-1");
			continue;
		}
		for(int i=1;i<=sqrt(n);i++)
		{
			if(n%i==0)
			{
				a[l++]=i;
				a[l++]=n/i;
			}
		}
		sort(a,a+l);
		int flag=0;
		for(int i=0;i<l;i++)
		{
			ll p=n-k*(k-1)*a[i]/2;
			if(p>(k-1)*a[i]&&(p%a[i]==0))
			{
				flag=1;
				for(ll j=1;j<k;j++)
					b[j]=a[i]*j;
				b[k]=p;
			}
			else if(p<=(k-1)*a[i])
				break;
		}
		if(flag)
			for(ll i=1;i<=k;i++)
				printf("%lld%c",b[i],i==k?'\n':' ');
	}
	return 0;
}