题目大意

定义传奇元组：
● (1,k)始终是传奇元组。
● 如果(n,k)是传奇元组，(n+k,k)与(nk,k)也是传奇元组。
我们想知道1≤n≤N,1≤k≤K时传奇元组(n,k)的数目。答案取模10^9+7。

解题思路

官方题解的思路写的很清晰（出题人宁太棒了）

通过题目条件，可以发现：一旦通过(n,k)->(nk,k)的操作来推出新的元组, n必定是k的倍数；而如果没有, 那么肯定是(xk+1,k)的形式。
所以，推出第一条结论：只有在满足n=1，n是k的倍数，或者n-1是k的倍数时，(n,k)是传奇元组。

因此，我们可以认为(n,k)是传奇元组，当且仅当n可以-k或/k，最后变成1。得到以下两种操作：

  • 如果n是k的倍数，即n=xk，那么可以减掉(x-1)个k，将n变为k，再/k为1。
  • 而如果n-1是k的倍数，即n=xk+1，那么x次除k就行。

详细做法参考官方题解：
图片说明

AC代码

#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
long long n,k,ans;
void find(long long n)
{
    long long i,j;
    for(i=2;i<=n && i<=k;i=j+1)
    {
        j=min(n/(n/i),k);
        (ans+=(j-i+1)%mod*(n/i)%mod)%=mod;
    }
}
int main()
{
    scanf("%lld%lld",&n,&k);
    find(n);find(n-1);
    printf("%lld\n",(ans+n+k-1)%mod);
    return 0;
}