题目大意 求这样一个最大的d使得
整理一下可以得到条件是
有注意到
的取值个数为
。
还是说明一下，设
。
1)当
时，显然至多
个取值。
2)当
时，显然有
，这个的取值个数也是
的。
因此可以发现当d等于一个值的时候可能和另一个d值的时候是等价的。
所以我们把所有的取值当成一个点，安插在数轴上，然后一段一段地进行枚举。因为每一段内的d都是等价的，所以只需要用每一段的左端点计算和，然后判断
是否在区间内，如果是就用它去更新答案。
1 /** 2 * Codeforces 3 * Problem#831F 4 * Accepted 5 * Time:997ms 6 * Memory:100400k 7 */ 8 #include <iostream> 9 #include <cstdio> 10 #include <ctime> 11 #include <cmath> 12 #include <cctype> 13 #include <cstring> 14 #include <cstdlib> 15 #include <fstream> 16 #include <sstream> 17 #include <algorithm> 18 #include <map> 19 #include <set> 20 #include <stack> 21 #include <queue> 22 #include <vector> 23 #include <stack> 24 #ifndef WIN32 25 #define Auto "%lld" 26 #else 27 #define Auto "%I64d" 28 #endif 29 using namespace std; 30 typedef bool boolean; 31 const signed int inf = (signed)((1u << 31) - 1); 32 const signed long long llf = (signed long long)((1ull << 63) - 1); 33 const double eps = 1e-6; 34 const int binary_limit = 128; 35 #define smin(a, b) a = min(a, b) 36 #define smax(a, b) a = max(a, b) 37 #define max3(a, b, c) max(a, max(b, c)) 38 #define min3(a, b, c) min(a, min(b, c)) 39 template<typename T> 40 inline boolean readInteger(T& u){ 41 char x; 42 int aFlag = 1; 43 while(!isdigit((x = getchar())) && x != ‘-‘ && x != -1); 44 if(x == -1) { 45 ungetc(x, stdin); 46 return false; 47 } 48 if(x == ‘-‘){ 49 x = getchar(); 50 aFlag = -1; 51 } 52 for(u = x - ‘0‘; isdigit((x = getchar())); u = (u << 1) + (u << 3) + x - ‘0‘); 53 ungetc(x, stdin); 54 u *= aFlag; 55 return true; 56 } 57 58 #define LL long long 59 60 int n; 61 LL C; 62 int* a; 63 vector<LL> seg; 64 65 template<typename T> 66 T ceil(T a, T b) { 67 return (a + b - 1) / b; 68 } 69 70 inline void init() { 71 readInteger(n); 72 readInteger(C); 73 seg.push_back(1); 74 a = new int[(n + 1)]; 75 for(int i = 1, x; i <= n; i++) { 76 readInteger(a[i]); 77 for(int j = 1; j * j <= a[i]; j++) 78 seg.push_back(j), seg.push_back(ceil(a[i], j)); 79 C += a[i]; 80 } 81 seg.push_back(llf); 82 } 83 84 LL res = 1; 85 inline void solve() { 86 sort(seg.begin(), seg.end()); 87 int m = unique(seg.begin(), seg.end()) - seg.begin() - 1; 88 for(int i = 0; i < m; i++) { 89 LL l = seg[i], r = seg[i + 1], temp = 0; 90 for(int i = 1; i <= n; i++) 91 temp += ceil((LL)a[i], l); 92 LL d = C / temp; 93 if(d >= l && d < r && d > res) 94 res = d; 95 } 96 printf(Auto"\n", res); 97 } 98 99 int main() { 100 init(); 101 solve(); 102 return 0; 103 }
Codeforces Round #424 (Div. 2, rated, based on VK Cup Finals) Problem F (Codeforces 831F) - 数论 - 暴力
原文：http://www.cnblogs.com/yyf0309/p/7193163.html