SRM 444

又在第一题上花了很多时间,这次更夸张。。用了20多分钟。。。最后提交时只有150分了。。
第二题,一看挺简单,就是求质因数的个数,然后看能被4的几次幂整除。
一开始匆忙写了一个,然后提交,400分。
代码如下:
              int getLevel(long long N) 
                  { 
                  
                  
int res = 0;
                                  
                  
for(long long i=2;i*i<=N;++i){                          
                           
while(N%i==0){
                                         res
++;
                                         N
/=i;
                                         }                                                                          
                           }
                                                            
                  
int r=0;
                  
while(res/4!=0){
                                  res
/=4;
                                  r
++;
                   }

                 
return r;
                  } 
后来一看,i*i<=N这时,N一直在变,应该保存下N或者直接求sqrt(N)。一开始不太确定sqrt能否处理long long,因此用相乘的方法。后来cha人的时候,发现一个也犯了同样的错误,马上构造56=2*2*2*7,cha掉
于是改成下面,提交,只有299分了。。。
              int getLevel(long long N) 
                  { 
                  
                  
int res = 0;
                  
long long T = N; //增加这一行            
                  for(long long i=2;i*i<=T;++i){                          
                           
while(N%i==0){
                                         res
++;
                                         N
/=i;
                                         }                                                                          
                   }
                                                            
                  
int r=0;
                  
while(res/4!=0){
                                  res
/=4;
                                  r
++;
                   }

                  
return r;
                  } 

结果还是被cha掉了。因为犯了一个严重的错误,没有算上最后一个质因数,这个质因数可能大于sqrt(N)。如88==2*2*2*11。
正确代码应该是
              int getLevel(long long N) 
                  { 
                  
                  
int res = 0;
                  
long long T = N;          
                  
for(long long i=2;i*i<=T;++i){                          
                           
while(N%i==0){
                                         res
++;
                                         N
/=i;
                                         }                                                                          
                   }
                          
                   
if(N!=1) res++//增加这一行
                                 

                  int r=0;
                  
while(res/4!=0){
                                  res
/=4;
                                  r
++;
                   }

                  
return r;
                  } 

最后房间只有一人过了第二题。
还好cha了4个,不然rating要跌不少了。。
还好rating还是涨了一点点。。
太粗心了,不然就应该能进div1了。。

posted on 2009-07-08 21:29 YZY 阅读(246) 评论(0)  编辑 收藏 引用 所属分类: TopCoderMiscellaneous


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


导航

<2009年7月>
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

统计

常用链接

留言簿(2)

随笔分类

随笔档案

搜索

积分与排名

最新评论

阅读排行榜