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