首页 > 其他 > 详细

P2261 [CQOI2007]余数求和

时间:2019-01-20 21:47:52      阅读:204      评论:0      收藏:0      [点我收藏+]

我是题面

题意还是很清晰,很容易理解

1e9范围明显不能暴力,除非你能把常数优化到\(\frac1 {10}\),但我实在想象不到用了这么多取模怎么把常数优化下去

我们可以把\(k\%i\)变成\(k-k/i*i\)(整除)

那么总的和也就从\(\sum_{i=1}^{n}k\%i\)变成了\(\sum_{i=1}^n k-k/i*i\),又可以转化为\(nk-\sum_{i=1}^n k/i*i\)

\(k/i\)的值只有有\(\sqrt k\)种,且相同的值都是连续出现的,所以我们可以直接利用等差数列求\(\sum_{i=1}^n k/i*i\)

下面放代码吧

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cctype>
#define ll long long
#define gc getchar
using namespace std;

inline ll read(){
    ll a=0;int f=0;char p=gc();
    while(!isdigit(p)){f|=p=='-';p=gc();}
    while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=gc();}
    return f?-a:a;
}ll n,k,ans;

int main(){
    n=read();k=read();
    for(int l=1,r;l<=n;l=r+1){
        if(k/l)r=min(k/(k/l),n);
        else r=n;
        ans+=k/l*(r-l+1)*(l+r)/2;
    }
    ans=n*k-ans;
    printf("%lld\n",ans);
    return 0;
}

不要抄袭哦

P2261 [CQOI2007]余数求和

原文:https://www.cnblogs.com/hanruyun/p/10296261.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!