Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

POJ 3511 Fermat's Christmas Theorem---线性筛素数+优化

Posted on 2009-08-24 20:22 Uriel 阅读(461) 评论(0)  编辑 收藏 引用 所属分类: POJ
这题做了一晚上。。TLE 10+次。。第二天优化了下,对于满足4C+1的数也事先存起来,最后减一下就行,瞬间32Ms。。
幸运的是组队赛时碰上了这题
/*Problem: 3511  User: Uriel 
   Memory: 12188K  Time: 32MS 
   Language: C  Result: Accepted
*/


#include
<stdio.h>
#include
<string.h>
#include
<stdlib.h>

int prime[80000],record[1000001],lenPr,i,j,sum1,sum2,L,U,k,sum[1000001],flag[1000001];
int main()
{
    memset(record, 
04000004);    
    lenPr
=0;
    record[
0]=1;
    record[
1]=1;
    sum[
0]=0;
    sum[
1]=0;
    flag[
0]=0;
    flag[
1]=0;
    
for (i = 2; i <=1000000; i++)
    
{
        
if (record[i]==0)
        
{
            lenPr
++;
            prime[lenPr
-1]=i;
        }

        
for(j=0;j<=lenPr-1;j++)
        
{
            
if (i*prime[j]>1000000)
                
break;
            record[i
*prime[j]] = 1;
            
if (i%prime[j]==0)
                
break;
        }

        
if(record[i]==0)sum[i]=sum[i-1]+1;
        
else
            sum[i]
=sum[i-1];
        
if(i%4==1 && record[i]==0)flag[i]=flag[i-1]+1;
        
else
            flag[i]
=flag[i-1];
    }

    
while(1)
    
{
        scanf(
"%d %d",&L,&U);
        
if(L==-1 && U==-1)exit(0);
        
if(L<0 && U<0)
        
{
            printf(
"%d %d 0 0\n",L,U);
            
continue;
        }

        sum1
=0;
        sum2
=0;
        k
=L;
        
if(k<0)k=0;
        sum1
=sum[U]-sum[k-1];
        sum2
=flag[U]-flag[k-1];
        
if(k<=2 && U>=2)sum2++;
        printf(
"%d %d %d %d\n",L,U,sum1,sum2);
    }

    
return 0;
}


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理