POJ1365 - Prime Land(质因数分解)

题目大意

给定一个数的质因子表达式,要求你计算机它的值,并减一,再对这个值进行质因数分解,输出表达式

题解

预处理一下,线性筛法筛下素数,然后求出值来之后再用筛选出的素数去分解。。。。其实主要就是字符串处理。。。

代码:

#include <stdio.h>
#include <string.h>
#include <math.h>
#define MAXN 10000
char str[MAXN],s[MAXN][7];
int prime[MAXN*5],cnt=0;
bool check[MAXN*5];
void get_prime()
{
int high=MAXN*5;
memset(check,false,true);
for(int i=2; i<=high; i++)
{
if(!check[i])
prime[cnt++]=i;
for(int j=0; j<cnt&&i*prime[j]<=high; j++)
{
check[i*prime[j]]=true;
if(i%prime[j]==0) break;
}
}
}
int get_sum(char *s)
{
int sum=0,len=strlen(s);
for(int i=0;i<len;i++)
sum=sum*10+s[i]-'0';
return sum;
}
int main()
{
char *p;
int ans;
get_prime();
while(gets(str))
{
bool first=false;
if(str[0]=='0') break;
int len=0;
p=strtok(str," ");
while (p!=NULL)
{
strcpy(s[len++],p);
p=strtok(NULL," ");
}
ans=1;
for(int i=0; i<len; i+=2)
{
int a,b;
a=get_sum(s[i]);
b=get_sum(s[i+1]);
ans*=(int)(pow(a*1.0,b*1.0));
}
ans--;
for(int i=cnt-1;i>=0&&ans!=1;i--)
{
if(ans%prime[i]==0)
{
int p=0;
while(ans%prime[i]==0)
{
p++;
ans/=prime[i];
}
if(!first)
{
printf("%d %d",prime[i],p);
first=true;
}
else
printf(" %d %d",prime[i],p);
}
}
printf("\n");
}
return 0;
}
上一篇:BZOJ3295: [Cqoi2011]动态逆序对(树状数组套主席树)


下一篇:DirectX中文手册