CF - 797A. k-Factorization - 思维+贪心+数学

题目描述： 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 100000 2 output 2 50000 input 100000 20 output -1 input 1024 5 output 2 64 2 2 2

题意概述：给你一个数字N要你把它分解成k个数相乘的形式。解题思路：我们知道一个数分解质因数的上限是sqrt(N)，那么直接将n分到sqrt部分，如果小于k则输出-1，否则贪心地把前sz - k个数合并即可。AC代码： #include <bits/stdc++.h> #define INF 0x3f3f3f3f #define maxn 100100 #define lson root << 1 #define rson root << 1 | 1 #define lent (t[root].r - t[root].l + 1) #define lenl (t[lson].r - t[lson].l + 1) #define lenr (t[rson].r - t[rson].l + 1) #define N 1111 #define eps 1e-6 #define pi acos(-1.0) #define e exp(1.0) using namespace std; const int mod = 1e9 + 7; typedef long long ll; typedef unsigned long long ull; vector<int> v; int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); long _begin_time = clock(); #endif int n, k; while (~scanf("%d%d", &n, &k)) { v.clear(); for (int i = 2; i * i <= n; i++) while (n % i == 0) { v.push_back(i); n /= i; } if (n > 1) v.push_back(n); if (v.size() < k) { puts("-1"); continue; } int sz = v.size(); int cur = 1; for (int i = 0; i + k < sz + 1; i++) cur *= v[i]; printf("%d", cur); for (int i = sz - k + 1; i < sz; i++) printf(" %d", v[i]); puts(""); } #ifndef ONLINE_JUDGE long _end_time = clock(); printf("time = %ld ms.", _end_time - _begin_time); #endif return 0; }