[关闭]
@ysner 2018-10-05T01:33:17.000000Z 字数 1029 阅读 2091

[Pa2013]Iloczyn

搜索 剪枝


题面

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

解析

这破题目卡常,删了一堆define快一倍
可以发现
所以顶多被分解成个不同正整数。

常规操作:找出所有约数然后枚举加剪枝。
然而我不会搜索啊,了一个小时。
要加这些剪枝。

只加这些剪枝的后果是要去掉程序中的和不必要的库(我还去了读入优化)。

然后上由变成时限一半。。。辣鸡卡常题。。。
然后写总结时又想到一个

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. using namespace std;
  5. const int N=2000;
  6. int n,k,sta[N],top,las,f[N][22];
  7. long long jc[22];
  8. int dfs(int x,int t,int s)
  9. {
  10. if(!t) return s==n;
  11. for(--t;x+t<=top;++x)
  12. {
  13. if(f[x][t]<0) return 0;
  14. if(1ll*f[x][t]*s>n) return 0;
  15. if(dfs(x+1,t,sta[x]*s)) return 1;
  16. }
  17. return 0;
  18. }
  19. int main()
  20. {
  21. ios::sync_with_stdio(false);
  22. int T;cin>>T;
  23. jc[0]=1;for(int i=1;i<=12;++i) jc[i]=jc[i-1]*i;
  24. while(T--)
  25. {
  26. cin>>n>>k;top=0;
  27. if(jc[k]>n||k>12) {puts("NIE");continue;}
  28. for(int i=1;i*i<=n;++i)
  29. if(n%i==0)
  30. {
  31. sta[++top]=i;
  32. if(i*i!=n) sta[++top]=n/i;
  33. }
  34. sort(sta+1,sta+1+top);
  35. for(int i=1;i<=top;++i)
  36. {
  37. long long t=1;
  38. for(int j=0;j<k&&i+j<=top;f[i][j++]=t)
  39. if(t>0)
  40. {
  41. t*=sta[i+j];
  42. if(t>n) t=-1;
  43. }
  44. }
  45. puts(dfs(1,k,1)?"TAK":"NIE");
  46. }
  47. return 0;
  48. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注