头部背景图片
Decaku 's Blog |
Decaku 's Blog |

Bzoj 1257 余数之和

描述:

$求\sum _{i=1}^nk \mod i, i \le n,k \le (10)^9$


思路:

$原式=\sum _{i=1}^n(k-k/i * i)=n * k-\sum _{i=1}^n(k/i*i) \\
k/i只有 \sqrt k个,所以可以整除分块。 \\
复杂度是 \sqrt n。
$


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**************************************************************
Problem: 1257
User: Decaku
Language: C++
Result: Accepted
Time:72 ms
Memory:1288 kb
****************************************************************/

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,k,sum;
int main()
{
ll ans=0;
scanf("%lld %lld",&n,&k);
sum=n*k;
if(n>k) n=k;
for(ll l=1,r; l<=n; l=r+1)
{
r=k/(k/l);
if(r>n) r=n;
ll tem=r*(r+1)/2-(l-1)*l/2;
ans+=tem*(k/l);
}
printf("%lld\n",sum-ans);
}
avatar Decaku 菜菜菜