2020牛客暑期多校训练营（第七场）H

Dividing

https://ac.nowcoder.com/acm/contest/5672/H

题目描述

The following rules define a kind of integer tuple - the Legend Tuple:
$(1, k)$ is always a Legend Tuple, where k is an integer.
if $(n, k)$ is a Legend Tuple, $(n + k, k)$ is also a Legend Tuple.
if $(n, k)$ is a Legend Tuple, $(nk, k)$ is also a Legend Tuple.
We want to know the number of the Legend Tuples $(n, k)$ where $1 \leqslant n \leqslant N$ , $1 \leqslant k \leqslant K$ .
In order to avoid calculations of huge integers, report the answer modulo $10^9+7$ instead.

输入描述

The input contains two integers $N$ and $K$ , $1 \leqslant N, K \leqslant 10^{12}$ .

输出描述

Output the answer modulo $10^9+7$ .

示例1

输入

3 3

输出

示例2

输入

3 9

输出

分析

所有 Legend Tuple 从 $(1,k)$ 出发，会产生 $(xk,k)$ 和 $(xk+1,k)$ 两种情况（ $x\in\mathbb N^\ast$ ）；其中， $(xk+1,k)$ 的情况经过一步操作可以变成 $(xk,k)$ 的情况。
显然，当且仅当 $k\mid (n-1)$ 或 $k\mid n$ 时， $(n,k)$ 为 Legend Tuple。
对于 $k\mid(n-1)$ 的情况，其贡献为 $\sum\limits_{k=1}^K\sum\limits_{n=1}^N\left[k\mid(n-1)\right]=\sum\limits_{k=1}^K\left\lfloor\frac{N-1}{k}\right\rfloor+K$ ； $\sum\limits_{k=1}^K\left\lfloor\frac{N-1}{k}\right\rfloor$ 为 $n\geqslant 2$ 的贡献， $K$ 为 $n=1$ 的贡献。
对于 $k\mid n$ 的情况，其贡献为 $\sum\limits_{k=1}^K\sum\limits_{n=1}^N [k\mid n]=\sum\limits_{k=1}^K\left\lfloor\frac{N}{k}\right\rfloor$ 。
对于两部分贡献，有 $(1,1),(2,1),\cdots,(N,1)$ 这部分的贡献是重复的，需要减去重复的一份贡献 $N$ 。
因此最终的答案为 $\sum\limits_{k=1}^K\sum\limits_{n=1}^N [k\mid n]=\sum\limits_{k=1}^K\left\lfloor\frac{N}{k}\right\rfloor+\sum\limits_{k=1}^K\sum\limits_{n=1}^N\left[k\mid(n-1)\right]=\sum\limits_{k=1}^K\left\lfloor\frac{N-1}{k}\right\rfloor+K-N$ 。可以用数论分块解决。
当然， $N=1$ 或 $K=1$ 时需要进行特判：当 $N=1$ ，答案为 $K$ ；当 $K=1$ ，答案为 $N$ 。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第七场）Problem H
Date: 8/28/2020
Description: Block
*******************************************************************/
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
ll N,K;
ll cal(ll n,ll k){
    //数论分块
    ll l,r;
    ll ans=0;
    for(l=1;l<=k;l=r+1){
        if(n/l==0){
            break;
        }
        r=min(k,n/(n/l));
        ans+=(r-l+1)*(n/l)%mod;
        ans%=mod;
    }
    return ans;
}
int main(){
    cin>>N>>K;
    if(N==1){
        cout<<K%mod<<endl;
    }else if(K==1){
        cout<<N%mod<<endl;
    }else{
        cout<<((cal(N,K)+cal(N-1,K)+K-N)%mod+mod)%mod<<endl;
    }
    return 0;
}

牛客暑期多校训练营题解文章被收录于专栏

收集牛客暑期多校训练营的题解