原题链接https://ac.nowcoder.com/acm/contest/5672/H

题目描述

定义一假传奇元组：

• （1，k）始终是传奇元组；
• 如果（n,k）是传奇元组，那么（n+k,k）和（n*k,k）也是传奇元组。

求当1≤n≤N，1≤k≤K时传奇元组的数量。
输出的答案对 取模。

输入描述

输入两个整数N,K。

输出描述

输出一个对 取模的答案。

样例

• 样例1

  输入

  3 3

  输出

  8

• 样例2

  输入

  3 9

  输出

  14

题解思路

这道题看上去十分骇人，因为数据范围达到了前所未有的1e12，如果想手动模拟那是肯定不行的。
如果你手动模拟了，就会发现，如果把传奇元组（n,k）看做点，那么你画出来的图可能是这样的（以为例）：

然后你就会一脸懵逼地看着这幅图并一脸懵逼地毫无思路然后一脸懵逼地做不出题目。

但这题其实可以推公式。
想不到吧！
但如果不思索之后推公式，在看了别人的公式后你会发现：
这是啥？.jpg
这又是啥？.jpg
因为你看到的可能是这样一坨堆代码（部分）：

sum=(sum+(j-i+1)%mod*y%mod)%mod;

ans=(n+k-1)%mod;
ans=(ans+work(n)+work(n-1))%mod;

其实在观察图片的过程中可以发现如果元组执行过（n,k）->（nk,k）的变化，则元组的第一个整数（即n）必然是第二个整数（即k）的倍数；若元组没执行过该变化，则元组必为（xk+1,k）的形式。
那么就可以开始我们的表演讨论了。
首先先讨论n是k的倍数的情况。不妨设n=xk。因为 ，所以x,k中至少有一个数小于 。在1e12的情况下枚举显然会T，但在1e6的情况下枚举则算是家常便饭了。所以只需要枚举其中一个数然后进行计算即可。
当n=xk+1时，同理。
假如n=1，直接统计即可（即为k）。
优化详见代码。

参考代码

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