题解 | #Forsaken遇到了毒瘤#

Forsaken遇到了毒瘤

https://ac.nowcoder.com/acm/problem/53408

在做本题之前你需要掌握的

快速幂与逆元
欧拉筛与线性求约数和
数论分块
一点点的数学推导能力

现在开始推导

\begin{aligned} &n \bmod d+m \bmod d \geq d \Longleftrightarrow \\ &n-d\left \lfloor \dfrac{n}{d}\right \rfloor + m- d\left \lfloor \dfrac{m}{d}\right \rfloor \geq d\Longleftrightarrow \\ &\left \lfloor \dfrac{n}{d}\right \rfloor + \left \lfloor \dfrac{m}{d}\right \rfloor + 1 \geq \left \lfloor \dfrac{n+m}{d}\right \rfloor \end{aligned}

看到这个向下取整这不立马联系到数论分块，那么我们就开始枚举d验证

那现在问题就只有求约数和了

\begin{aligned} &\sum_{x=1}^n \sum_{d|x}^{} d = \sum_{d=1}^n d\sum_{x=1}^{\left \lfloor \frac{n}{d}\right \rfloor}=\sum_{d=1}^nd\left \lfloor \dfrac{n}{d}\right \rfloor\sum_{d=1}^nd \end{aligned}

如果我们对这个式子预处理1e7，对于大于1e7的进行分块计算，时间复杂度就是能接受的代码如下

#include<bits/stdc++.h>
using namespace std;
#define sb cout << "sb" << endl;
const int N=1e7+5;
using ll = long long;
ll sd[N],num[N];///sd是约数和
const int Mod=1e9+7;
int cnt;
int prime[N];
bool vis[N];
void init()
{
    sd[1]=1;
    for(int i=2;i<N;++i)
    {
        if(!vis[i])
        {
            prime[++cnt]=i;
            sd[i]=i+1;
            num[i]=i+1;
        }
        for(int j=1;j<=cnt&&i*prime[j]<N;++j)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                num[i*prime[j]]=num[i]*prime[j]+1;
                sd[i*prime[j]]=sd[i]/num[i]*(num[i*prime[j]]);
                break;
            }
            sd[i*prime[j]]=sd[i]*sd[prime[j]];
            num[i*prime[j]]=1+prime[j];
        }
    }
    for(int i=1;i<N;++i)
        sd[i]=(sd[i-1]+sd[i])%Mod;
}
ll qpow(ll a,ll b)
{
    ll r=1;
    while(b)
    {
        if(b&1)r=a*r%Mod;
        a=a*a%Mod;
        b>>=1;
    }
    return r;
}
ll inv2=qpow(2,Mod-2);
ll cal(ll x)
{
    return x*(x+1)%Mod*inv2%Mod;
}
ll getsum(ll x)
{
    if(x<N)return sd[x];
    ll ans=0;
    for(ll l=1,r;l<=x;l=r+1)
    {
        r=x/(x/l);
        ans+=(cal(r)-cal(l-1))%Mod*(x/l)%Mod;
        ans%=Mod;
    }
    return ans;
}
int main()
{
    init();
    ll n,m;cin >> n >> m;
    if(n>m)swap(n,m);
    ll res=0;
    for(ll l=1,r;l<=n;l=r+1)
    {

        r=min(n/(n/l),m/(m/l));
        r=min(r,(n+m)/((n+m)/l));
        //cout << l << ' ' << r << endl;
        if((n/l+m/l+1)<=(n+m)/l)
        {
            res+=(getsum(r)-getsum(l-1))%Mod;
            res%=Mod;
        }
    }
    //cout << res << endl;
    for(ll l=n+1,r;l<=m;l=r+1)
    {
        r=min(m/(m/l),(n+m)/((n+m)/l));
        if((m/l)+1<=(m+n)/l)
            res+=(getsum(r)-getsum(l-1))%Mod;
    }
    res+=(getsum(n+m)-getsum(m))%Mod;
    cout << (res%Mod+Mod)%Mod <<'\n';
}
/*
1000000000 1000000000
*/

题外话：我也不知道那个复杂度怎么算出来的，出题人写的题解也很神奇，这种用不完全预处理嗯降复杂度的做法，对于一个数学题来说，我觉得出的挺差劲的

题解 | #Forsaken遇到了毒瘤#

在做本题之前你需要掌握的

全站热榜