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