A simple Blog for wyx I've been down the bottle hoping.
3733: [Pa2013]Iloczyn 暴搜
发表于: | 分类: Oi | 评论:0 | 阅读:166

我想了一个小时然后发现自己的$dp$ GG了,我满怀对数学的敬畏之心翻看题解,看完题解社会观崩塌,大概从NOIP之后已经好久没做搜索题了……老年选手表示思想江化

然后直接搜是会T的,你需要一些剪枝……大概这里说的非常清楚……

具体来说就是你乱搞一些方法比如预处理约数一节几个约数凑到这之类的方法使得这个东西跑的比较快……

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;  
typedef long long LL;
const int N = 1e5+5;

inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int n,m,k;
int g[N];
LL F[N][30];
  
bool DFS(int t,int x,int tmp) {
    if(!x) return tmp == n;
    x --;
    while(1) {
        if(t + x > m) return false;
        if(F[t][x] > n || F[t][x]*tmp > n) return false;
        if(DFS(t+1,x,tmp*g[t])) return true;
        t ++;
    }
}  

int main () {
    int Q; cin >> Q; while(Q --) {
        cin >> n >> k;
        if((n == 1 &&  k >= 2 )|| (n >= 3 && k >= n)) { puts("NIE"); continue; }
        if(k <= 2) { puts("TAK");  continue; }
        int t; m = 0;
        for(t=1;t*t<n;++t) if(n%t==0) g[++m] = t, g[++m] = n/t;
        if(t*t==n) g[++m] = t; sort(g+1,g+m+1);
        LL tmp = 1;
        for(int i=1;i<=m;++i,tmp=1) for(int j=0;j<k && i+j<=m;F[i][j++] = tmp)  if(tmp <= n) tmp *= g[i+j];
        if(DFS(1,k,1)) puts("TAK");
        else puts("NIE");
    }
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP