原题链接

考察：推导公式

蓝书是将本题归纳到约数里,我实在没看出来这道题和约数有啥关系

这道题计算k%(1~n)的值,实际上是求k - [k/i]*i的值.转化后将式子累加得到n*k-累加和[k/i]*i.

n*k是已知的式子,i在循环里枚举,唯一要求的是[k/i].一个个求是肯定不行的,因此需要求得某些规律

假设n==10,k==10时,可以发现：

k/i	10	5	3	2	2	1	1	1	1	1
i	1	2	3	4	5	6	7	8	9	10

当i>10,k/i就==0,因此不再画出

在i=4~5和6~9的时候,我们可以发现k/i是连续的.我们可以将这段通过求和公式累加而避免循环.通过推导发现连续区间的下界在k/[k/i].上界就是下界+1.

然后就可以通过求和公式计算答案

易错：

1. 当我们计算连续区间的和时,要将tmp放在前面,这样式子就被转化为long long防止溢出
2. 计算下界的时候要防止下界超出n范围外

 1 #include <iostream>
 2 using namespace std;
 3 typedef long long ll;//251698457 3813613
 4 int main()
 5 {
 6     ll n,k;
 7     scanf("%lld%lld",&n,&k);
 8     ll ans = n*k;
 9     for(int i=1,ed;i<=n;i=ed+1)
10     {
11         ll tmp = k/i;
12         ed = k/i==0?n:min(k/(k/i),n);
13         ans-=tmp*(i+ed)*(ed-i+1)/2;//把tmp放前面这样式子就会转化成long long型 
14     }
15     printf("%lld\n",ans);
16     return 0;
17 }