Description
给出整数\(n,k\),计算\(G(n,k)=\sum\limits_{i=1}^n=k \ mod \ i\),\(1<=n,k<=1e9\)
Solution
将k mod i展开可以得到
\(k - i*\lfloor \frac{k}{i} \rfloor\)
将求和式子展开可以得到
\(\sum\limits_{i=1}^n=n*k-\sum\limits_{i=1}^n i*\lfloor\frac{k}{i} \rfloor\)
利用整除分块,可以发现,对于相同的\(\lfloor\frac{k}{i} \rfloor\),即每个区间\(l 到 r\),每次只需要再对i求和即可
即每次计算\((r-l+1)*\lfloor \frac{k}{i} \rfloor * (l+r)/2\)
Note
在分块的时候误写为r=N/(N/i)
导致调试耽误大量时间,而且交了四发才发现
for (ll l = 1, r; l <= N; l = r + 1) {
if (l > K) {
break;
}
r = min(N, K/(K/l));
ans -= (r - l + 1)*(K/l)*(l + r)/2;
}
Code
//https://www.luogu.com.cn/problem/P2261
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#define mem(a,b) memset(a,b,sizeof(a))
#define debug cout<<0<<endl
#define ll long long
const int MAXN = 1e2 + 10;
const int MOD = 1e9 + 7;
using namespace std;
ll ans = 0;
void solve(ll N, ll K) {
ans = N*K;
for (ll l = 1, r; l <= N; l = r + 1) {
if (l > K) {
break;
}
r = min(N, K/(K/l));
ans -= (r - l + 1)*(K/l)*(l + r)/2;
}
cout << ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll N, K; cin >> N >> K;
solve(N, K);
return 0;
}
原文链接: https://www.cnblogs.com/ez4zzw/p/12898048.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/348916
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!