Posted on 2008-10-31 17:04
Hero 閱讀(127)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1 // 1023 C++ Accepted 0.015 137 KB URAL
2
3 /*
4 對于任意n，若n有約數i(包含n),那么i-1定為可行解，
5 應為一開始處于mod i 的平衡狀態，然后先手會打破這個狀態，
6 只要后手不斷恢復平衡狀態即可必勝。
7 */
8 #include <stdio.h>
9 #include <stdlib.h>
10 #include <string.h>
11 #include <math.h>
12
13 int inn ;
14
15 int main()
16 {
17 while( scanf( "%d", &inn ) != EOF )
18 {
19 int i ; int maxi = sqrt( inn*1.0 ) + 1 ;
20 for( i=3; i<=maxi; i++ ) if( 0 == inn % i ) break ;
21
22 if( i > maxi )
23 {//inn為質數或者質數*2
24 if( (inn & 1) ) printf( "%d\n", inn-1 ) ;
25 else
26 if( inn/2-1 > 1 )
27 printf( "%d\n", inn/2 - 1 ) ;
28 else
29 printf( "%d\n", inn-1 ) ;
30 }
31 else
32 printf( "%d\n", i-1 ) ;
33 }
34
35 return 0 ;
36 }