@ysner
2018-10-05T01:33:17.000000Z
字数 1029
阅读 2091
搜索
剪枝
给定正整数和,问能否将分解为个不同正整数的乘积。
这破题目卡常,删了一堆define快一倍
可以发现。
所以顶多被分解成个不同正整数。
常规操作:找出所有约数然后枚举加剪枝。
然而我不会搜索啊,了一个小时。
要加这些剪枝。
只加这些剪枝的后果是要去掉程序中的和不必要的库(我还去了读入优化)。
然后上由变成时限一半。。。辣鸡卡常题。。。
然后写总结时又想到一个
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2000;
int n,k,sta[N],top,las,f[N][22];
long long jc[22];
int dfs(int x,int t,int s)
{
if(!t) return s==n;
for(--t;x+t<=top;++x)
{
if(f[x][t]<0) return 0;
if(1ll*f[x][t]*s>n) return 0;
if(dfs(x+1,t,sta[x]*s)) return 1;
}
return 0;
}
int main()
{
ios::sync_with_stdio(false);
int T;cin>>T;
jc[0]=1;for(int i=1;i<=12;++i) jc[i]=jc[i-1]*i;
while(T--)
{
cin>>n>>k;top=0;
if(jc[k]>n||k>12) {puts("NIE");continue;}
for(int i=1;i*i<=n;++i)
if(n%i==0)
{
sta[++top]=i;
if(i*i!=n) sta[++top]=n/i;
}
sort(sta+1,sta+1+top);
for(int i=1;i<=top;++i)
{
long long t=1;
for(int j=0;j<k&&i+j<=top;f[i][j++]=t)
if(t>0)
{
t*=sta[i+j];
if(t>n) t=-1;
}
}
puts(dfs(1,k,1)?"TAK":"NIE");
}
return 0;
}