CodeForces - 616E Sum of Remainders

标签: 两眼题  mod是真的骚  多试几次就过了  数论??  区间

Sum of Remainders

+传送门+


◇题意◇

给定nm,求ans=i=1m(nmodi)

n,m(1n,m1013)
断绝一切念想对吧


◇解析◇

做前内心戏

(模求和??)&&(1e13)

模求和,难道需要我不会的运算定律???我强大的算术基本定理可不是瞎吹的!暴力吧?!

O(1013)…….

不对不对,肯定是我看错了,擦眼睛再看一遍:
O(1013)(看得脸都绿了)

对对对对对,你没有看错,就是1013
“断绝一切念想”。
对,这就是想更优算法的理由!

严肃的分析

Ⅰ.模求和

对于一个可以说在编程路途中给我们无数麻烦的算术钉子户“mod”大爷来说,在各种题目中躺在AC道路上挡道是再平常不过的了,因此处理“mod”是看完题的第一想法。处理成什么呢???这时,我们的老熟人“”“/”在路上打了个招呼,于是,我们坚定地绕路走:

nmodi=ninians=i=1m(nmodi)ans=nmi=1mini

Ⅱ.1e13

(Ⅰ)中的分析乍一眼看很有道理,当我考试想出来这些时我以为我能AC,但抹了眼睛再看1e13!!
完全没有解决啊!!!
不能放弃啊,我们把注意力集中到ans的表达式上。

ans=nmi=1mini

nm显然是容易算的,因此:有一定计算难度的是后面的
i=1mini

多年计算的经验告诉我们ni中有许多值是一样的,而拥有相同商的i也应该是连续的,于是[1,m]构成了由许多个具有不同ni值的区间组成的大区间

这里写图片描述
这样我们就把6次计算收缩到4个可利用等差数列求和公式和乘法计算的区间,进行有效的收缩,而当n,m更大,收缩效果会更明显

Ⅲ.寻找区间

感觉已经距AC很近了!(真的是这样吗)
注意上图中每一段区间的开始和结束
:1,1——:2,2——:3,4——:5,6
(如果m=8:5,8
很容易的发现所有的区间构成一个连续的数列,即[1,m]
换句话说,就是当前区间的起点就是上一个的结尾+1(这不是废话吗)
关于找结尾我们有很多种算法
⑴显然是m的因数(从小到大),不好写且不优;
⑵设区间i开头为li,结尾ri

li=ri1+1ri=n/nli

显然l1=1,r1=1,所以[1,m]就可以完美的递推表达出来了。

最后一个区间结尾是m,不要写得陶醉停不下来

Ⅳ.计算答案

根据上文定义,对于[li,ri]所有值中有相同xi(下取整过后的商)
开始时

ans=nm

对于这段区间ans应该减去
(rili+1)(li+ri)2xi

干完所有的区间,就ok了


◇代码◇

#include<cstdio>
#include<algorithm>
using namespace std;
const int Mod=int(1e9)+7;
#define LL long long

LL n,m;
LL ans,l=1,r,x;

LL dcsl(LL x) { 
    return (x%Mod)*((x+1)%Mod)/2%Mod;
}
LL Dcsl(LL i,LL j) {
    return dcsl(j)-dcsl(i-1);
}
LL Add(LL x,LL y) {
    return ((x%Mod)+(y%Mod))%Mod;
}
LL Sub() {
    ans=Add(ans,Mod-(x*(Dcsl(l,r)))%Mod);
}

int main()
{
    scanf("%lld%lld",&n,&m);
    ans=((n%Mod)*(m%Mod))%Mod;
    m=min(m,n);
    //当n>i,x=0,没必要再算
    for(;l<=m;l=r+1) {
        x=n/l;
        r=min(m,n/x);
        Sub();
    }
    printf("%lld",ans);
}
再说两句

1.mod才是最骚的。
2.第二句。


Thanks For Reading!

原文链接:加载失败,请重新获取