Detachment（数论）

思路：
先按照正常构造自然数：
$S=2\times 3\times \ldots \times \left( n-\Delta x\right) \times \left( n-\Delta x+1\right) \times \ldots \times n$
一般会多出一个数$\Delta x$ ($\Delta x\leq n$)
$\begin{aligned}S=2\times 3\times \ldots \times \left( n-\Delta x\right) \times \left( n-\Delta x+2\right) \times \ldots \times \left( n+1\right) \\ \left( \Delta x <n-1\right) \end{aligned}$
$\begin{aligned}S=3\times 4\times \ldots \times \left( n+1\right) \\ \left( \Delta x=n-1\right) \end{aligned}$
$\begin{aligned}S=3\times 4\times \ldots \times \left( n+2\right) \\ \left( \Delta x=n\right) \end{aligned}$
首先通过前缀和，前缀积，线性逆元进行数据预处理
之后通过二分优化找到$\Delta x$，最后带入公式分类讨论即可
代码：

#include<iostream>
#define LL long long
#define fo(i,a,b) for(int i=a;i<b;i++)
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
using namespace std;
const LL mod=1e9+7;
const int N=1e5+5;
LL sum[N],mul[N],inv[N];
void init(){
    sum[1]=0;mul[1]=1;inv[1]=1;//1的逆元是1
    fo(i,2,N){
        sum[i]=sum[i-1]+i;
        mul[i]=(mul[i-1]%mod)*i%mod;
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    } 
}
LL t,x,l,r,mid;
LL ans=0;
int main(){
    init();
    scanf("%d",&t);
    while(t--){
        scanf("%lld",&x);
        if(x<5){
            printf("%lld\n",x);
            continue;
        }
        l=2;r=N;
        while(l<r){
            mid=(l+r+1)>>1;
            if(sum[mid]<=x)l=mid;
            else r=mid-1;
        }
        LL res=x-sum[l];
        if(res==(l-1) || res==l)ans=(mul[l]*inv[2])%mod*(res+2)%mod;
        else ans=mul[l]*inv[l-res+1]%mod*(l+1)%mod;
        printf("%lld\n",ans);
    }
    return 0;
}

本文地址：https://blog.csdn.net/qq_45550375/article/details/107193330