Posted on 2008-10-31 17:04
Hero 阅读(107)
评论(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 }