取模求助
查看原帖
取模求助
941431
Autream楼主2024/3/23 10:12

直接推的公式 (n−m+1+n−⌊nm⌋×m+1)×⌊nm⌋2+1\frac{(n-m+1+n-\lfloor\frac{n}{m}\rfloor \times m +1)\times \lfloor\frac{n}{m}\rfloor}{2}+1(化简后的 ∑k⌊nm⌋(n−k×m+1)+1\sum \limits ^{\lfloor\frac{n}{m}\rfloor}_k (n-k\times m+1)+1),但是取模不知道为什么会溢出

#include<bits/stdc++.h>
#define arrout(a,n) rep(i,1,n)std::cout<<a[i]<<" "
#define arrin(a,n) rep(i,1,n)std::cin>>a[i]
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dep(i,x,n) for(int i=x;i>=n;i--)
#define erg(i,x) for(int i=head[x];i;i=e[i].nex)
#define dbg(x) std::cout<<#x<<":"<<x<<" "
#define mem(a,x) memset(a,x,sizeof a)
#define all(x) x.begin(),x.end()
#define arrall(a,n) a+1,a+1+n
#define PII std::pair<int,int>
#define m_p std::make_pair
#define u_b upper_bound
#define l_b lower_bound
#define p_b push_back
#define CD const double
#define CI const int
#define int long long
#define il inline
#define ss second
#define ff first
#define itn int
CI N=1e5+5,MOD=1e9+7;
int n,m,inv[N];
int qpow(int x,int y) {
    int ans=1;
    while(y) {
        if(y&1) {
            ans=ans*x%MOD;
        }
        x=x*x%MOD;
        y>>=1;
    }
    return ans%MOD;
}
void pre() {
    rep(i,1,m) {
        inv[i]=qpow(i,MOD-2);
    }
}
signed main() {
    std::cin>>n>>m;
    inv[1]=1; 
    for(int i=2; i<=m; i++) {
        inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;
    }
    std::cout<<((n-m+1+n-(n/m)*m+1)*(n/m)%MOD)*inv[2]%MOD+1;
    return 0;
}
2024/3/23 10:12
加载中...