H-Diving

链接：https://ac.nowcoder.com/acm/contest/5672/H
来源：牛客网

题意：

给出N,K,根据题目要求(1,n)是 Legend Tuple,假设(n,k)是 Legend Tuple,那么(n+k,k)也是,如果(n,k)是 Legend Tuple,那么(nk,k)也是 Legend Tuple,1<=n<=N,1<=k<=K的范围内求满足上述条件的 Legend Tuple个数

solution：

1,k;
k,k;
1+k,k;
k*k,k;
……
每两行都是由前面的两行推出来，且这样构造出来的解不会重复，因此我们只要进行整数分块求解，并将多余的部分去掉就行了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k;
const int mod=1e9+7;
ll res=0;
ll get(ll n,ll k)
{
    ll ans=0;
    for(ll i=1;i*i<=n;i++)
    {
        if(n%i==0)
        {
            if(i>=3&&i<=k)ans++;
            ll t=n/i;
            if(t!=i&&t>=3&&t<=k)ans++;
        }
    }
    return ans;
}
int main()
{
    cin>>n>>k;
    if(k<=2)
        cout<<(n*k%mod);
    else if(n<=1)
        cout<<k%mod;
    else
    {
        for(ll l=3,r;l<=k;l=r+1)
        {
            if(n/l==0)r=k;
            else r=min(n/(n/l),k);
            res=(res+(r-l+1)*(n/l)%mod)%mod;
        }
        res=(res*2+2*n)%mod;
        res=(res+k-2-get(n,k)+mod)%mod;
        cout<<res;
    }
    return 0;
}