Codeforces 797A - k-Factorization

A. k-Factorization

题目链接：http://codeforces.com/problemset/problem/797/A

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Given a positive integer n, find k integers (not necessary distinct) such that all these integers are strictly greater than 1, and their product is equal to n.

Input

The first line contains two integers n and k (2 ≤ n ≤ 100000, 1 ≤ k ≤ 20).

Output

If it's impossible to find the representation of n as a product of k numbers, print -1.

Otherwise, print k integers in any order. Their product must be equal to n. If there are multiple answers, print any of them.

Examples

input

5 1

output

input

5 2

output

-1

input

1024 5

output

2 64 2 2 2 
题目大意：输入两个数n和k,找k个大于1的整数，使他们的乘积为n，输出这k个数（如果有多个，输出任意一组），如果没有，输出-1。
方法：把n分解成质因数的乘积，并把这些质因数保存在数组里。如果质因数的个数c小于k,输出-1；否则，输出前k-1个质因数和k到c个质因数的乘积（这样就刚好k个）。
代码：

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

const int N=1e5;

int main()

{

    int n,k;

    cin>>n>>k;

    int f[N];

    int c=;

    for(int i=;i<=n;i++)

    {

        while(n%i==)

        {

            n/=i;

            f[c++]=i;

        }

    }

    if(c<k)cout<<-<<endl;

    else

    {

        for(int i=;i<k-;i++)

        cout<<f[i]<<' ';

        int sum=;

        for(int i=k-;i<c;i++)

        sum*=f[i];

        cout<<sum<<endl;

    }

    return ;

}

巴特西

Codeforces 797A - k-Factorization

最新文章

热门文章