题意分析
对于正整数 $n,k$，求能否将 $n$ 划分为 $k$ 个不同的正整数的乘积，多测。
搜索
观察数据范围，可以发现 $1\leq k\leq 20$，拆出来数的个数不会太多，因此考虑 DFS。
很容易写出一个暴力 DFS 的判断函数：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//last用于防止重复
bool check(int n,int k,int last=0){
if(k==1){//边界：拆分为1个数
return n>last;
}
for(int i=last+1;i<=n;i++){
if(n%i==0){
if(check(n/i,k-1,i)){
return true;
}
}
}
return false;
}
但是这样显然是过不了的，实测只能获得 $\text{54pts}$。
因此我们考虑剪枝。
剪枝之一
在 check() 中枚举因数 $i$ 可以优化，因为 $i$ 如果取到 $\sqrt[k]{n}$ 以上的时候是一定无解的。
那么优化后的判断函数为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool check(int n,int k,int last=0){
if(k==1){
return n>last;
}
int Max=pow(n,1.0/k);
for(int i=last+1;i<=Max;i++){
if(n%i==0){
if(check(n/i,k-1,i)){
return true;
}
}
}
return false;
}
剪枝之二
显然，能够拆分为 $k$ 个正整数的乘积的数必须大于 $k!$。
而众所周知，阶乘的增长是非常迅速的，由计算器可得 $13!=6227020800>10^9$。
因此当 $k\geq13$ 的时候，直接输出 NIE 即可。
其他优化
意义不大，因为上面两个简单易懂的剪枝已经足以通过此题，但可以参考。
比如说预处理出 $1\sim12$ 的阶乘，每次二分检验能否直接输出 NIE。
或者说 $\mathcal O(\sqrt n)$ 求出 $n$ 的因数，然后在因数中枚举。
AC 代码
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
35
36
37
38
39
40
41
42
43
44
45
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
bool check(int n,int k,int last=0){
if(k==1){
return n>last;
}
int Max=pow(n,1.0/k);
for(int i=last+1;i<=Max;i++){
if(n%i==0){
if(check(n/i,k-1,i)){
return true;
}
}
}
return false;
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
int T;
scanf("%d",&T);
while(T--){
int n,k;
scanf("%d %d",&n,&k);
printf("%s\n",(k<=12 && check(n,k)?"TAK":"NIE"));
}
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
