Detachment
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 392 Accepted Submission(s):
131
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,a2
, … (x= a1+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 ( aiaj
when i≠j).
2.Make this multidimensional space size s as large as possible
(s= a1∗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)
test cases.
Then T lines follow. Each line contains one integer
x.
1≤T≤10^6, 1≤x≤10^9
to be greatest product before modulo 10^9+7.
4
inv[i]=(mod-mod/i)*inv[mod%i]%mod;求出每个数的逆元 2 3 4 5 6 7 8 9 ......l +r
b[i]=(b[i-1]*i)%mod;
比如2+r>l
结果只需要ans=b[l]*inv[2]*(2+r);
因为2在做累积进行了取模运算 所以不能直接除2,要乘以她的逆元
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<string.h>
#include<map>
#define INF 1000000000
#define LETTER 26
#define SIZE 45000
#define pi 3.14159265358979
typedef long long ll;
typedef unsigned long long LL;
using namespace std;
const long long mod=INF+;
int a[SIZE],inv[SIZE];
ll b[SIZE];
int low,high,mid;
void f(){
a[]=;
b[]=;
inv[]=;
for(int i=;i<=SIZE;i++){
a[i]=a[i-]+i;
b[i]=(b[i-]*i)%mod;
inv[i]=(mod-mod/i)*inv[mod%i]%mod; }
}
void erfen(int n){
low=,high=SIZE;
while(low+<high){
mid=(low+high)>>;
if(n>=a[mid]) low=mid;
else high=mid;
}
}
int main(){
int i,j,k;
int t;
int n;
f();
ll ans;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
if(n<=){cout<<n<<endl;continue;}
erfen(n);
int l=low,r=n-a[l];
if(+r>l){
ans=b[l]*inv[]%mod*(+r)%mod;
}
else{
k=l+-r;
ans=b[l]*inv[k]%mod*(l+)%mod;
}
printf("%lld\n",(ans+mod)%mod); } }