首页 > 代码库 > BZOJ3733: [Pa2013]Iloczyn
BZOJ3733: [Pa2013]Iloczyn
3733: [Pa2013]Iloczyn
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 85 Solved: 15
[Submit][Status]
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
15 2
24 4
24 5
Sample Output
TAK
TAK
NIE
TAK
NIE
HINT
Source
题解：
这题我还没AC，但我先说一下目前的做法。。。
先分解质因数，然后我们“离散化”这些因数，用一个map，然后问题就是可不可以从这m个约数里挑出k个，使得乘积为n。
我们利用01背包的思想，一个一个放即可。复杂度目测有点高。。。T成翔。。。
代码：
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 100000 26 27 #define maxm 500+100 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 43 #define mod 1000000007 44 45 using namespace std; 46 47 inline int read() 48 49 { 50 51 int x=0,f=1;char ch=getchar(); 52 53 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 54 55 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 56 57 return x*f; 58 59 } 60 int a[maxn],b[maxn],c[maxn]; 61 map<int,int>mp; 62 bool v[maxn][25]; 63 inline bool check(int x) 64 { 65 int y=sqrt(x); 66 for2(i,2,y)if(x%y==0)return 0; 67 return 1; 68 } 69 70 int main() 71 72 { 73 74 freopen("input.txt","r",stdin); 75 76 freopen("output.txt","w",stdout); 77 78 int cs=read(); 79 while(cs--) 80 { 81 int n=read(),k=read(),t=sqrt(n),m=0; 82 if(k==1){puts("TAK");continue;} 83 if(k==2){if(n==1)puts("NIE");else puts("TAK");continue;} 84 if(k==3){if(check(n))puts("NIE");else puts("TAK");continue;} 85 for1(i,t) 86 if(n%i==0)a[++m]=i,b[m]=n/i; 87 if(a[m]==b[m]) 88 { 89 for1(i,m-1)a[m+i]=b[m-i],c[i]=m+m-i,c[m+m-i]=i;c[m]=m; 90 m+=m-1; 91 } 92 else 93 { 94 for1(i,m)a[m+i]=b[m+1-i],c[i]=m+m+1-i,c[m+m+1-i]=i; 95 m<<=1; 96 } 97 for1(i,m) 98 { 99 for1(j,k+1)v[i][j]=0;100 mp[a[i]]=i;101 }102 v[1][1]=1;103 for2(i,2,m)104 for3(j,c[i],1)105 {106 ll x=(ll)a[i]*(ll)a[j];107 if(x>n)continue;int y=mp[(int)x];108 if(!y)continue;109 for1(l,k)110 if(v[j][l])v[y][l+1]=1;111 }112 if(v[m][k]||v[m][k+1])printf("TAK\n");else printf("NIE\n");113 for1(i,m)mp[a[i]]=0;114 } 115 116 return 0;117 118 }
我再思考一下能不能降下复杂度？预处理？
BZOJ3733: [Pa2013]Iloczyn
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。