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

Dividing

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

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;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-10 14:10
啊啊啊啊好幸福,妈妈是我找工作发疯前的一束光
榕城小榕树:你是我见过最幸福的牛客男孩
点赞 评论 收藏
分享
舂锋:不能投什么岗都用一份简历,一般都是要看企业的岗位需求来写职业技能或者是项目经历,跟岗位相关的就写多一点。
点赞 评论 收藏
分享
06-07 19:59
门头沟学院 C++
补药卡我啊😭:都快15年前的了还在11新特性
你的简历改到第几版了
点赞 评论 收藏
分享
评论
3
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务