codeforces] ECR19 A. k-Factorization [数论]

链接：Codeforces Educational Codeforces Round 19 A. k-Factorization

题意

给你两个正整数 n, k。

判断是否存在k个数相乘，使其乘积等于n。
如果不存在，输出-1。
如果存在，再以任何你喜欢的顺序输出这k个数。
（当然他们之间应以空格分隔）

分析

题目不难，应该有很多种方法解答这个问题。

我直接说一下我的思路：

既然要得到k个数相乘，那么这k个数肯定是尽量越小越好。
（比如n能被6整除，那尽量把6拆成2和3。）
这里面有点贪心的感觉。因为如果剩下的n越大，那满足k个数的概率也就越大。

所以这道题我直接从2开始循环判断是否能够做n的因子。
如果可以就直接存下来，n除去当前因子，然后继续判断这个因子。
如果不行，那再判断他的后一个（新因子 = 因子+1）

依次这样判断，直到找不到因子了或者已经够个数了为止。

（当已经找到k-1个因子时，就可以直接把剩下的n当做最后一个数，而不用继续做下去了。）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <cstdio>
#include <vector>
using namespace std;
int n, k;
int main()
{
    while( ~scanf( "%d %d", &n, &k ) ){
        vector< int > ans;  //用来存这k个数
        int j = 0;  //保存当前因子个数
        for( int i = 2; i <= n; i++ ){
            if( n % i == 0 ){   //若能整除则存下来
                if( ++j == k ){ //已经存够k-1个数，则直接存入剩下的n
                    ans.push_back( n );
                    break;
                }
                n /= i;
                ans.push_back( i );
                i--;
            }
        }
        if( j != k )    puts( "-1" );
        else{
            int sz = ans.size();
            printf( "%d", ans[ 0 ] );
            for( int i = 1; i < sz; i++ ){
                printf( " %d", ans[ i ] );
            }
            puts( "" );
        }
    }
    return 0;
}

小结

毕竟签到题，比较得简单，如果大家有更简单的方法可以留言或者Q我。

数论
数论, codeforces