319
POJ1142
本来是道简单题 却让我做的那么挫 = = 一开始RE 后来MLE 再后来TLE 然后WA 我真是没法说了 自己这么弱吗 但是我怎么都没想到Wa那么些次原来是m定义应该是100000000 我少了一位 不知道为什么会出现这种错误
我的思路是先打出来个素数表 然后再通过素数表里的素数对x 不断的取质因子 然后如果x等于1 那么证明质因子都取出来了 如果x不是1 那么证明x是一个素数没有被除 然后再加上那个最后判断是否相等 如果x是素数不符合题意
看了一下 我这么做还是很快的 0MS 200K
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define max 10500
int Sum(int x)
{
int ans=0,m=100000000;
while(x>0)
{
if(x>=m)
ans+=x/m,x%=m;
m/=10;
}
return ans;
}
bool isprime[max];
int prime[max],nprime;
void getprime()
{
long long i,j;
nprime=0;
memset(isprime,1,sizeof(isprime));
isprime[1]=0;
for(i=2; i<max; i++)
{
if(isprime[i])
{
prime[++nprime]=i;
for(j=i*i; j<max; j+=i)
isprime[j]=0;
}
}
}
bool pdans(int x)
{
int a,b=0,q=1,temp=x;
a=Sum(x);
while(prime[q]*prime[q]<=x)
{
while(x%prime[q]==0)
{
b+=Sum(prime[q]);
x/=prime[q];
}
q++;
}
if(x>1)
b+=Sum(x);
if(a==b&&x!=temp)
return 1;
return 0;
}
int main()
{
int n;
getprime();
while(~scanf("%d",&n)&&n)
{
while(!pdans(++n));
printf("%d\n",n);
}
return 0;
}
最后更新：2017-04-04 07:03:23