Dividing

题目

通过题目条件，可以发现：一旦通过(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就行。

• #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
  ",(ans+n+k-1)%mod);
      return 0;
  }