首页 > 代码库 > CodeForces 797A k-Factorization

CodeForces 797A k-Factorization

质因数分解。

分解一下质因数,如果个数小于$k$个,则无解,否则把多出来的合成一个数。

#include <iostream>#include <cstdio>#include <cmath>#include <cstring>#include <string>#include <queue>#include <stack>#include <vector>#include <algorithm>using namespace std;int b[100010],sz;int n,k;int a[100010];vector<int>ans;bool prime(int x){	for(int i=2;i*i<=x;i++)	{		if(x%i==0) return 0;	}	return 1;}void init(){	for(int i=2;i<=100000;i++)	{		if(prime(i)) b[sz++] =i;	}}int main(){	init();	scanf("%d%d",&n,&k);	for(int i=0;i<sz;i++)	{		while(n%b[i]==0)		{			ans.push_back(b[i]);			n=n/b[i];		}		if(n==1) break;	}	if(ans.size()<k)	{		printf("-1\n");	}	else 	{		for(int i=0;i<k-1;i++)		{			printf("%d ",ans[i]);		}		int p=1;		for(int i=k-1;i<ans.size();i++)		{			p=p*ans[i];		}		printf("%d\n",p);	}	return 0;}

 

CodeForces 797A k-Factorization