題目鏈接

Problem Description

In a highly developed alien society, the habitats are almost infinite dimensional space.In the history of this planet,there is an old puzzle.You have a line segment with x units’ length representing one dimension.The line segment can be split into a number of small line segments: a1,a2a1,a2, … (x= a1+a2a1+a2+…) assigned to different dimensions. And then, the multidimensional space has been established. Now there are two requirements for this space: 1．Two different small line segments cannot be equal ( ai≠ajai≠aj when i≠j).2．Make this multidimensional space size s as large as possible (s= a1?a2a1?a2*…).Note that it allows to keep one dimension.That’s to say, the number of ai can be only one.Now can you solve this question and find the maximum size of the space?(For the final number is too large,your answer will be modulo 10^9+7)

Input

The 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^9

Output

Maximum 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

AC

• 一個數字分成多個不相同的數字相乘，首先分成1不合理，因為1乘以一個數結果不增加，從2枚舉所有X可以分出的連續數字，最后可能會剩余幾個數字，可以把剩余的數字看成N個1，剩下任務就是將這N個1分出去，從最后一個數字開始往前每個數字加1，這樣能保證連續的情況下乘積最大，這樣就有兩種情況，剩下的數字能分完和不能分完（多了個1），例如8 = 2 +3 +3，最后一個3分給前面兩個數字之后多了個1，這個1就分到最后一個數字上，例如8 = 2 +3 +2，這樣剛好分完
• 數據規模大，一共有1e6的詢問，時間要求在2秒，所以每次最好O（1）算出結果，觀察上面的思路，最后的得到的數字，就是部分連續的數字相乘，可以用階乘打表處理，另外存在相除的情況，所以也要逆元打表，判斷最后一個數字是否能分完，需要用到sum前綴

#include <iostream> #include <stdio.h> #include <map> #include <vector> #include <set> #include <cstring> #include <cmath> #include <algorithm> #define N 100005 #define ll long long using namespace std; ll mod = 1e9 + 7; ll inv[N], sum[N], jie[N]; void init() {// 逆元打標 inv[1] = 1;for (int i = 2; i < N; ++i) {inv[i] = inv[mod % i] * (mod - mod / i) % mod;}// sum記錄前綴之和 sum[2] = 2;for (int i = 3; i < N; ++i) {sum[i] = sum[i - 1] + i;}// 階乘打表 jie[2] = 2;for (int i = 3; i < N; ++i) {jie[i] = jie[i - 1] * i;jie[i] %= mod;} } int main() { #ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin); #endifinit();int t;scanf("%d", &t) ;while (t--) {ll x, ans;scanf("%lld", &x);// 找到第一個大于等于sum的位置 int pos = lower_bound(sum, sum + N, x) - sum;while (sum[pos] > x) pos--;int cha = x - sum[pos];// X剛好分完 if (cha == 0) ans = jie[pos];// 多出來pos個1 （不能分完） if (cha == pos) ans = (jie[pos] * inv[2] % mod) * (pos + 2) % mod;// 多出來的1小于pos（可以分完） if (cha < pos)ans = jie[pos + 1] * inv[pos + 1 - cha] % mod;// X小于5，保持原來的長度最好 if (ans == 0) ans = x; printf("%lld\n", ans); }return 0; }

總結

以上是生活随笔為你收集整理的HDU Problem - 5976 Detachment（逆元，阶乘打表，数学）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。