去年长春最简单一题 二分啊 错了好多遍 有个大坑 是个圆心处的1 可选可不选
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<cmath> 7 using namespace std; 8 #define LL __int64 9 LL s; 10 int main() 11 { 12 int i,j; 13 while(scanf("%I64d",&s)!=EOF) 14 { 15 LL maxz = s-1,m1 = 1,m2 = s-1; 16 for(i = 2; i <= 40 ; i++) 17 { 18 LL low = 1,high = s,m; 19 double ty = 1,ts=0; 20 while(low<=high) 21 { 22 m = (low+high)/2; 23 ts = 0,ty=1; 24 for(j = 0 ; j <= i ; j++) 25 { 26 ts+=ty; 27 ty*=m; 28 if(ts>s) break; 29 } 30 if(ts>s) 31 high = m-1; 32 else if(ts<s) 33 low = m+1; 34 else break; 35 } 36 if(s==ts&&maxz>i*m) 37 { 38 maxz = i*m; 39 m1 = i; 40 m2 = m; 41 } 42 low = 1,high = s,ts=0,ty=1; 43 while(low<=high) 44 { 45 m = (low+high)/2; 46 ts = 0,ty=m; 47 for(j = 1 ; j <= i ; j++) 48 { 49 ts+=ty; 50 ty*=m; 51 if(ts>s) break; 52 } 53 if(ts>s) 54 high = m-1; 55 else if(ts<s) 56 low = m+1; 57 else break; 58 } 59 if(s==ts&&maxz>i*m) 60 { 61 maxz = i*m; 62 m1 = i; 63 m2 = m; 64 } 65 } 66 printf("%I64d %I64d ",m1,m2); 67 } 68 return 0; 69 }