BZOJ 3733 [Pa2013]Iloczyn 模拟爆搜

Description

给定正整数n和k,问能否将n分解为k个不同正整数的乘积

Input

第一行一个数T(T<=4000)表示测试组数 
接下来T行每行两个数n(n<=10^9),k(k<=20)

Output

输出T行,若可以被分解,输出”TAK”否则输出”NIE”

Sample Input

3

15 2

24 4

24 5 
Sample Output

TAK

TAK

NIE

题解 
搜索＋剪枝，先求出所有因数，然后暴力搜索，剪枝就是如果后面最小的k个数当前数相乘大于n就退出。

orz wsj大佬

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #include<iostream>

 #include<cstdio>

 #define N 10007

 #define ll long long

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch>''||ch<''){if (ch=='-') f=-;ch=getchar();}

     while(ch<=''&&ch>=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}

     return x*f;

 }

 int n,k,tot,p[N];

 ll f[N][];

 bool dfs(int now,int k,int tmp)

 {

     if (!k) return tmp==n;

     k--;

     for (;now+k<=tot;now++)

     {

         if (f[now][k]<) return ;

         if (f[now][k]*tmp>n) return ;

         if (dfs(now+,k,tmp*p[now])) return ;

     }

     return ;

 }

 inline void solve()

 {

     n=read();k=read();tot=;

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

         if (n%i==)

         {

             p[++tot]=i;

             if (i*i!=n) p[++tot]=n/i;

         }

     sort(p+,p+tot+);

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

     {

         ll tmp=;

         for (int j=;j<k&&i+j<=tot;f[i][j++]=tmp)

             if (tmp>)

             {

                 tmp*=p[i+j];

                 if (tmp>n) tmp=-;

             }

     }

     if (dfs(,k,)) puts("TAK");

     else puts("NIE");

 }

 int main()

 {

     int Case=read();

     while (Case--)

         solve();

 }