InputThe first line is an integer T,meaning the number of test cases.
Then T lines follow. Each line contains one integer x.
1≤T≤10^6, 1≤x≤10^9OutputMaximum s you can get modulo 10^9+7. Note that we wants to be greatest product before modulo 10^9+7.
Sample Input
1 4
Sample Output
4
题意概括：
给一个数 N ，可以把它分解成若干个不相同的数 N = a1+a2+a3+...... ，求最大的 S = a1*a2*a3*.......
分多少个随意，也可以不分。
解题思路：
一开始以为是规律题，
后来推了无果，笔纸模拟到 11 发现一个神奇的贪心
要是乘积最大化，那可分的数越多越好。
而每一个数可分的数字数量是有规律的。
x1 = 1, s1 = 1;
x2 = 2, s2 = 2;
x3 = 3, s3 = 3;
x4 = 4, s4 = 4;
x5 = 2+3, s5 = 2*3;
x6 = 2+4 [2+(3+1)], s6 = 2*4;
x7 = 3+4 [(2+1) + (3+1)], s7 = 3*4;
x8 = 3+5 [(2+1) + (3+1+1)], s8 = 3*5;
x9 = 2+3+4, s9 = 2*3*4;
x10 = 2+3+5 [2+3+(4+1)], s10 = 2*3*5;
x11 = 2+4+5 [2+(3+1)+(4+1)], s11 = 2*4*5;
...
如何构造贪心显而易见了，
假如有一个数让你拆成两个要求积最大，肯定是拆成两个一样的，如果拆成n个，肯定就是拆成这个数/n，如果没说几个，肯定都拆成几个3就拆成几个三，剩下的拆成2.这个题要求不能一样的，所以肯定就是2,3,4这样排列了，从2开始让它变小，这样数量会最多，每次加一就是让他越来越接近。所以用前缀和记录，如果有剩余的话，肯定是从后往前逐个+1，而且剩余的那个数最多=2,3,4...最大的那个数，举个例子会发现有两种情况：1.比如2*3*4*5余下5，相等。最优就是3*4*5*7，就是每个数都加一遍，然后会剩下一个1，加给最后一个，总的来说就是 除以2，乘上t+2,（t是最后一个数的值）；2.不相等，2,3,4,5，余2，最优就是2,3,5,6，就是用3的阶乘*6的阶乘除以4的阶乘，因为数量太多，不能一个一个乘，就用前缀积相除，数字太大，就要用逆元了。。然后用二分优化下。。
数据量大，要用前缀积+逆元求，用前缀和优化，二分找小于当前值的最接近的前缀和，求余数
https://blog.csdn.net/qq_34374664/article/details/53466435
此题关键在于得出如何能使乘积s最大
按照以往经验，必然是取一段连续自然数能够使得乘积最大，而这段连续自然数可从2开始(为啥不从1开始?从1开始还不如将这个1给这段连续自然数的最后一个数)，
于是我们可以得到形如2+3+4+...+k(k=2,3,...)的式子，而x是10^9内的任意整数，我们不可能恰好能够凑成连续自然数之和，可能会多出△x
而这个△x的值，我可以保证它的范围为0≤△x≤k，相信大于等于0还是好理解的，为什么会小于等于k呢?因为当它大于k时，原式不是可以增加一项?即2+3+4+...+k+(k+1)
那么多出来的△x怎么处理呢?显然是从后往前均摊给连续自然数中的(k-1)个数，为啥从后往前?因为若我们从前往后，总是会使连续自然数重复，不好处理
于是，在我们分配完△x之后，我们大致会得到下述两种式子:
显然，我们要计算此结果，可以借助阶乘，而阶乘中缺失的项，我们除掉就可以了，那么便会涉及除法取模，显然需要用到乘法逆元
做法讲解完毕，以下是为什么连续段乘积最大的大概证明:
AC code：
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #include <cstring> 5 #define LL long long 6 using namespace std; 7 const int MAXN = 1e5+5; 8 const int Mod = 1e9+7; 9 10 LL mul[MAXN], sum[MAXN]; 11 void init() 12 { 13 mul[1] = 1; 14 sum[1] = 0; 15 for(int i = 2; i < MAXN; i++){ 16 sum[i] = sum[i-1] + i; //前缀和 17 mul[i] = (i*mul[i-1])%Mod; //前缀积 18 } 19 } 20 21 LL inv(LL a, int b) //费马小定理求逆元 22 { 23 LL ans = 1; 24 while(b){ 25 if(b&1) ans = (ans*a)%Mod; 26 a = (a*a)%Mod; 27 b >>= 1; 28 } 29 return ans; 30 } 31 32 int main() 33 { 34 int t, x; 35 init(); 36 scanf("%d", &t); 37 while(t--){ 38 scanf("%d", &x); 39 if(x == 1){ 40 puts("1"); 41 continue; 42 } 43 int l = 2, r = MAXN, mid, p; 44 while(l <= r){ 45 mid = (l+r)/2; 46 if(sum[mid] <= x) p = mid, l = mid+1; 47 else r = mid-1; 48 } 49 // printf("%d\n", p); 50 int num = x - sum[p]; 51 LL ans = 0; 52 if(num == p) 53 ans = (mul[p]*inv(2, Mod-2)%Mod*(p+2))%Mod; 54 else 55 ans = (mul[p+1]*inv(mul[p+1-num], Mod-2)%Mod*mul[p-num])%Mod; 56 printf("%lld\n", ans); 57 } 58 return 0; 59 } 60 61 F - Detachment
2016 ACM/ICPC亚洲区大连站 F - Detachment 【维护前缀积、前缀和、二分搜索优化】
原文：https://www.cnblogs.com/ymzjj/p/9865052.html
