codeforces-797A-k-Factorization

蔚落 2022-05-24 11:08 15阅读 0赞

A. k-Factorization

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

Copy

100000 2

output

Copy

2 50000

input

Copy

100000 20

output

Copy

-1

input

Copy

1024 5

output

Copy

2 64 2 2 2

题目大意：给你个数n让你找到k个大于1的数并使它们的乘积等于n；

思路：素数唯一分解定理

代码:

#include<map>
    #include<stack>
    #include<queue>
    #include<cmath>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define ll long long
    int mark[11100],a[11100],aa[11111];
    void prime()
    {
        int i,j,q=0;
        memset(mark,0,sizeof(mark));
        mark[1]=1;
        for(i=2; i<=31000; i++)
        {
            if(mark[i]==0)
            {
                for(j=i*i; j<=31000; j+=i)
                {
                    mark[j]=1;
                }
            }
        }
        for(i=2; i<=31000; i++)
        {
            if(mark[i]==0)
            {
                a[q++]=i;
            }
        }
    }
    int main()
    {
        int m,n;
        prime();
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            memset(aa,0,sizeof(aa));
            int i=0,k=0;
            if(m==1)
            {
                printf("%d\n",n);
                continue;
            }
            i=0;
            while(1)
            {
                if(n==1)
                    break;
                if(k==m-1)
                {
                    aa[k++]=n;
                    break;
                }
                if(n%a[i]==0)
                {
                    aa[k++]=a[i];
                    n/=a[i];
                }
                else
                    i++;
            }
            if(k==m)
            {
                printf("%d",aa[0]);
                for(i=1; i<k; i++)
                {
                    printf(" %d",aa[i]);
                }
                printf("\n");
            }
            else
                printf("-1\n");
        }
        return 0;
    }