【BZOJ3733】[Pa2013]Iloczyn （搜索）

题面

题解

把约数筛出来之后，直接爆搜，再随便剪枝就过了。

最近一句话题解倾向比较严重

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

#define ll long long

#define MAX 50000

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int ys[MAX],tot,K,n;

bool dfs(int x,int t,int s)

{

	if(t==K&&s==n)return true;

	if(t>=K)return false;

	if(x==tot+1)return false;

	if(tot-x+1<K-t)return false;

	for(int i=x,j=t+1,ss=s;j<=K;++i,++j)

		if(1ll*ss*ys[i]>n)return false;

		else ss=1ll*ss*ys[i];

	if(dfs(x+1,t,s))return true;

	if(1ll*s*ys[x]<=n)

		if(dfs(x+1,t+1,s*ys[x]))return true;

	return false;

}

int main()

{

	int T=read();

	while(T--)

	{

		n=read();K=read();tot=0;

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

			if(n%i==0)

			{

				ys[++tot]=i;

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

			}

		sort(&ys[1],&ys[tot+1]);

		if(dfs(1,0,1))puts("TAK");

		else puts("NIE");

	}

	return 0;

}

巴特西

【BZOJ3733】[Pa2013]Iloczyn （搜索）

【BZOJ3733】[Pa2013]Iloczyn （搜索）

题面

题解

最新文章

热门文章