2020牛客多校第7场H-Dividing[思维+数论分块]

题目大意：

解题思路：很明显满足条件的点是 $n\%k==0||n\%k==1$
1.因为 $n$是从 $1$开始的如果一直乘以 $k[n=n*k]$那么 $n\%k==0$
2.如果是一直加 $k[n=1+x*k][加了x次]---->n\%k==1$

求 $n\%k==0$的对数: $n=x*k-->相当于n\in[1,n],k\in[1,k]有多少n和k是整数倍关系？$
$\sum_{i=1}^k\sum_{j=1}^{\lfloor {n\over i} \rfloor}[ans++]$
化简：
$\sum_{i=1}^k{\lfloor {n\over i} \rfloor}$
同理：求 $n\%k==1$
$\sum_{i=2}^k{\lfloor {n - 1\over i} \rfloor}$:注意这里i从2开始因为从1开始统计重复了

我们这里只考虑了 $n>=k$的情况当 $n<k$时候也可以：就是 $n=1，k>1$就是 $ans+=k-1$

#include <iostream>
#include <cstdio>
#include <stack>
#include <sstream>
#include <limits.h>
#include <vector>
#include <map>
#include <cstring>
#include <deque>
#include <cmath>
#include <iomanip>
#include <queue>
#include <algorithm>
#include <set>
#define mid ((l + r) >> 1) 
#define Lson rt << 1, l , mid
#define Rson rt << 1|1, mid + 1, r
#define ms(a,al) memset(a,al,sizeof(a))
#define log2(a) log(a)/log(2)
#define _for(i,a,b) for( int i = (a); i < (b); ++i)
#define _rep(i,a,b) for( int i = (a); i <= (b); ++i)
#define for_(i,a,b) for( int i = (a); i >= (b); -- i)
#define rep_(i,a,b) for( int i = (a); i > (b); -- i)
#define lowbit(x) ((-x) & x)
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define INF 0x3f3f3f3f
#define LLF 0x3f3f3f3f3f3f3f3f
#define hash Hash
#define next Next
#define count Count
#define pb push_back
#define f first
#define s second
using namespace std;
const int N = 310, mod = 1e9 + 7;
const long double eps = 1e-10;
const long long maxn = 1e15;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef pair<double,double> PDD;
template<typename T> void read(T &x)
{x = 0;char ch = getchar();ll f = 1;while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) 
{read(first);read(args...);
}
int main()
{int t;ll n,m,i=0,j=0,ans=0;cin>>n>>m;for(i=1;i<=m;i=j+1){ll a=n;if(i>a) break;j=min(a/(a/i),m);ans = (ans+(j-i+1)*(a/i))%mod;}for(i=2;i<=m;i=j+1){ll a=n-1;if(i>a) break;j=min((a)/(a/i),m);ans = (ans+(j-i+1)*(a/i))%mod;}ans=(ans+m-1)%mod;//ans=(ans+n)%mod;printf("%lld\n",ans % mod);  return 0;// cout << sqrt(maxn) << endl;
}