学步园

TAG  高精度

以前的经验，转换成int数组时用比较大的进制程序会比较快。比如1000进制的话，123456789转换成{123,456,789}的一个数组。

刚开始用了100000进制，没考虑到模除的结果比较大，用int结果会溢出的(╬▔ ω▔) wa了好多次，还查不出有什么问题。。。

google一下，看了某题解“不过大牛们说,百进制TLE,千进制AC,万进制WA”才恍然大悟。

杯具。。(╬▔ ω▔)

1.13s，有点慢。。。

/* source code of submission 435783, Zhongshan University Online Judge System */<br /> #include <stdio.h><br /> #include <memory.h><br /> #include <string.h><br /> const int p10[]={1,10,100,1000};<br /> const int N=1000000;<br /> bool isprime[N+1];<br /> char K[102];<br /> int hp[40];<br /> int L,len;<br /> int ans;<br /> void makeprime()<br /> {<br /> memset(isprime, true, sizeof(isprime) );<br /> for (int i=2; i<=N; ++i )<br /> {<br /> if ( isprime[i] )<br /> {<br /> for (int j=2; j*i<=N; ++j)<br /> {<br /> isprime[j*i]=false;<br /> }<br /> }<br /> }<br /> }<br /> void trans()<br /> {<br /> memset(hp, 0, sizeof(hp) );<br /> len=(strlen(K)-1)/3;<br /> int slen=strlen(K);<br /> for (int i=0; i<=len; ++i)<br /> {<br /> for (int j=1; j<=3 && slen-i*3-j>=0; ++j)<br /> {<br /> hp[i]+=p10[j-1]*(K[slen-i*3-j]-'0');<br /> }<br /> }<br /> }<br /> bool module(int x)<br /> {<br /> int ret=0;<br /> for (int i=len; i>=0; --i)<br /> {<br /> ret=(hp[i]+ret*1000)%x;<br /> }<br /> return ret;<br /> }<br /> bool check()<br /> {<br /> for (int i=2; i<L; ++i)<br /> {<br /> if ( !isprime[i] )<br /> {<br /> continue;<br /> }</p> <p> if ( module(i)==0 )<br /> {<br /> ans=i;<br /> return false;<br /> }<br /> }<br /> return true;<br /> }<br /> int main(int argc, char *argv[])<br /> {<br /> makeprime();<br /> while ( scanf("%s%d",K, &L)&& L!=0 )<br /> {<br /> trans();<br /> if ( check() )<br /> {<br /> printf("GOOD/n");<br /> }<br /> else<br /> {<br /> printf("BAD %d/n",ans);<br /> }<br /> }<br /> return 0;<br /> }<br />