59
POJ 1365 小整数分解
题意：给你一个数的，素数次幂乘积形式的表示让你求出这个数减一的素数次幂乘积的表示形式。
这题就是麻烦，首先打一个素数表，然后把输入存成字符串形式，在还原成数，再分解，再输出。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 50000
char c[maxn];
int num[maxn],nprime,prime[maxn],ans[maxn];
bool isprime[maxn];
void getprime() //素数打表
{
memset(isprime,1,sizeof(isprime));
nprime=1;
long long i,j;
for(i=2; i<maxn; i++)
if(isprime[i])
{
prime[++nprime]=i;
for(j=i*i; j<maxn; j+=i)
isprime[j]=0;
}
}
int getnum() //字符串还原成数组
{
memset(num,0,sizeof(num));
int len=strlen(c);
int j=0;
for(int i=0; i<len; i++)
{
if(c[i]==' ')
j++;
else
num[j]=num[j]*10+c[i]-'0';
}
return j;
}
long long getans(int n) //数组还原数-1
{
int ans=1;
for(int i=0; i+1<=n; i+=2)
for(int j=0; j<num[i+1]; j++)
ans*=num[i];
return ans-1;
}
int solve(long long ansnum) //把减一的数再分解
{
int d,num=0;
long long x=ansnum;
memset(ans,0,sizeof(ans));
for(d=2; prime[d]<=ansnum; d++);
for(int i=d; i>=2; i--)
if(x%prime[i]==0)
{
ans[num]=prime[i];
while(x%prime[i]==0)
ans[num+1]++,x/=prime[i];
num+=2;
}
return num;
}
void output(int n) //数组分解之后的数
{
for(int i=0; i<n; i++)
if(i<n-1)
printf("%d ",ans[i]);
else
printf("%d\n",ans[i]);
}
int main()
{
getprime();
while(gets(c)!=NULL)
{
int n=getnum();
if(n==0)
break;
long long ansnum=getans(n);
int num=solve(ansnum);
output(num);
}
return 0;
}
最后更新：2017-04-03 21:13:14