我希望你是我独家记忆

一段永远封存的记忆,随风而去
posts - 263, comments - 31, trackbacks - 0, articles - 3
   :: 首页 :: 新随笔 ::  :: 聚合  :: 管理

SGU_CONTEST30_A(Everlasting...?)

Posted on 2009-09-27 09:37 Hero 阅读(151) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

简单题 素数测试

 1 // A  .CPP_VS Accepted 269 ms 8339 kb 
 2 
 3 #include <stdio.h>
 4 #include <stdlib.h>
 5 
 6 const int size = 1100000 ;
 7 int isPrime[size+100] ;
 8 
 9 int QUEprime[size] ;
10 int QUEsize ;
11 
12 int ina, inb ;
13 
14 void Init_isPrime()
15 {
16     isPrime[0= isPrime[1= 0 ;
17     forint i=2; i<size; i++ ) isPrime[i] = 1 ;
18 
19     int maxi = size / 2 ;
20     forint i=2; i<=maxi; i++ )
21     {
22         if!isPrime[i] ) continue ;
23         forint j=2; i*j<size; j++ )
24         {
25             isPrime[i*j] = 0 ;
26         }
27     }
28 
29     QUEsize = 0 ;
30     forint i=2; i<size; i++ )
31     {
32         if( isPrime[i] )
33         {
34             QUEsize ++ ;
35             QUEprime[QUEsize] = i ;
36         }
37     }
38 }
39 
40 int main()
41 {
42     Init_isPrime() ;
43 
44     while( scanf( "%d %d"&ina, &inb ) != EOF )
45     {
46         int suma = 0 ; int sumb = 0 ;
47         int prima = 0 ; int primb = 0 ;
48 
49         forint i=1; i<=QUEsize; i++ )
50         {
51             if( QUEprime[i] > ina ) break ;
52             if0 == ina % QUEprime[i] )
53             {
54                 suma += QUEprime[i] ;
55                 prima = QUEprime[i] ;
56                 while0 == ina % QUEprime[i] )
57                 {
58                     ina = ina / QUEprime[i] ;
59                 }
60             }
61         }
62 
63         forint i=1; i<=QUEsize; i++ )
64         {
65             if( QUEprime[i] > inb ) break ;
66             if0 == inb % QUEprime[i] )
67             {
68                 sumb += QUEprime[i] ;
69                 primb = QUEprime[i] ;
70                 while( inb % QUEprime[i] ) 
71                 {
72                     inb = inb / QUEprime[i] ;
73                 }
74             }
75         }
76 
77         int outa = prima - (suma - prima) ;
78         int outb = primb - (sumb - primb) ;
79 
80         if( outa >= outb )
81         {
82             printf( "a\n" ) ;
83         }
84         else
85         {
86             printf( "b\n" ) ;
87         }
88     }
89 
90     return 0 ;
91 }

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