Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Problem Description - 题目描述
在一个高度发达的外星文明中，有着近乎无限维度的生存空间。 在这颗星球的历史中，有道古老的谜题。 你有一条长x个单位长度的线段表示一个维度。这条线段可以被拆分为若干小线段：a1,a2, … (x= a1+a2+…)并分配为不同的维度。然后，多维空间就建立起来了。现在，这个空间有两个限制： 1．两个不同的小线段不能相等( ai≠aj when i≠j)。 2．多维空间的大小s要尽可能大(s= a1?a2*...)。注意，各维度只能保持一种。也就是说，ai的值必须唯一。 现在的你能解决这个问题并找出最大的空间吗？（结果可能很大，输出模10^9+7）
第一行为一个整数T，描述测试用例的数量。 随后T行。每行有一个整数x。 1≤T≤10^6, 1≤x≤10^9
Output - 输出
s的最大值需要模10^9+7。注意，模10^9+7是在获得最大乘积后。
Sample Input - 输入样例
1 4
Sample Output - 输出样例
4
题解
先猜一发最优策略：2+3+4+5+6+……
然后再猜一发对于剩下数的分配策略：每次从后往前，对每个数+1。
接着就发现似乎策略就是这样了。
后面需要做的处理：求前n项和，求前n项积。
最后遇到（a % mod）/（b % mod）的时候需要用逆元。
把（a/b）%mod转化为（a * inv b）%mod 不嫌弃速度的话可以用费马小定理：
mod为质数时，inv a = a^(mod - 2)
或者用其他方法…………
代码 C++
1 #include <cstdio> 2 #include <algorithm> 3 #define mod 1000000007 4 #define mx 44722 5 __int64 mul[mx] = { 1 }, sum[mx]; 6 __int64 qMod(__int64 a, int n){ 7 __int64 opt = 1; 8 while (n){ 9 if (n & 1) opt = (opt*a) % mod; 10 n >>= 1; 11 a = (a*a) % mod; 12 } 13 return opt; 14 } 15 __int64 lr(int l, int r){//[l, r] 16 return (mul[r] * qMod(mul[l - 1], mod - 2)) % mod; 17 } 18 void rdy(){ 19 int i, j; 20 for (i = 1, j = 2; i < mx; ++i, ++j){ 21 sum[i] = j + sum[i - 1]; 22 mul[i] = (j * mul[i - 1]) % mod; 23 } 24 } 25 int main(){ 26 rdy(); 27 int t, len, w, l, r; 28 __int64 x, opt; 29 scanf("%d", &t); 30 while (t--){ 31 scanf("%I64d", &x); 32 if (x < 5) opt = x; 33 else{ 34 len = std::upper_bound(sum, sum + mx, x) - sum - 1; 35 r = len + (x - sum[len]) / len; 36 w = (x - sum[len]) % len; 37 opt = lr(r - len + 1, r - w); 38 if (w) opt *= lr(r + 2 - w, r + 1), opt %= mod; 39 } 40 printf("%I64d\n", opt); 41 } 42 return 0; 43 }
原文：http://www.cnblogs.com/Simon-X/p/6279899.html
