2020牛客暑期多校训练营（第七场）H-Dividing （数学/分块整除）

Dividing

题目大意：定义(1,k)为传奇元组

• 如果(n,k)是传奇元组的话，(n*k,k)也是传奇元组
• 如果(n,k)是传奇元组的话，(n+k,k)也是传奇元组

解题思路：

题意第二条可以转换一下，因为n只能加k或者乘k，而n起始为1，所以n一定为k的倍数或者n%k==1,即(n+k,k)可以转换成 (n*k+1,k)-->n-1是k的倍数。

所以问题就变成了 n=x * k 或者 n-1=x * k;
这里要注意一下 n 和 k 的范围是不一样的，如果k大于等于n，那么运算到底即可，而k小于n时，运算到k截断即可--> j=min(n/(n/i),k);。
剩下就是整除分块的问题了，跑一下模板就odk了。

Code：

#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include<cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#define eps 1e-5
using namespace std;
typedef long long ll;
const int mod=1e9+7;

int main(){

    int t;
    ll n,m,i=0,j=0,ans=0;
    cin>>n>>m;
    for(i=2;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);  
    return 0;
}