【BZOJ1257】余数之和(数论分块,暴力)
暴力 数论 分块 余数
2023-09-11 14:14:41 时间
【BZOJ1257】余数之和(数论分块,暴力)
题解
Description
给出正整数n和k,计算j(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值,其中k mod i表示k除以i的余数。例如j(5, 3)=3 mod 1 + 3 mod 2 + 3 mod 3 + 3 mod 4 + 3 mod 5=0+1+0+3+3=7
Input
输入仅一行,包含两个整数n, k。
Output
输出仅一行,即j(n, k)。
Sample Input
5 3
Sample Output
7
HINT
50%的数据满足:1<=n, k<=1000 100%的数据满足:1<=n ,k<=10^9
题解
很Interesting的一道题目
所求为
\[\sum_{i=1}^n{k}\ \%\ {i}
\]
而这个式子可以再改一下
\[\sum_{i=1}^nk-i*(k\ div \ i)
\]
其中\(div\)是整除
前面的\(n*k\)直接先算出来
后面的东西,很容易观察到,\(i\)是单增的
而\(k/i\)在一段范围内是不会变化的
因此,每次求出这一段范围,然后直接计算等差数列即可
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
inline int read()
{
int x=0,t=1;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return x*t;
}
long long ans,n,k;
int main()
{
n=read();k=read();
ans=n*k;
for(long long l=1,r=0;l<=n;l=r+1)
{
if(k/l)r=min(n,k/(k/l));
else r=n;
ans-=(k/l)*(r-l+1)*(l+r)>>1;
}
printf("%lld\n",ans);
return 0;
}
相关文章
- hdu 1814 字典序最小的2sat(暴力深搜)
- 【BZOJ1800】[AHOI2009]飞行棋(暴力)
- 程序员很暴力,请远离
- 【BZOJ3251】树上三角形 暴力
- 【BZOJ1053】[HAOI2007]反素数ant 暴力
- JS Leetcode 220. 存在重复元素 III 题解分析,暴力解法与桶排序
- 暴力探测蓝牙设备工具redfang
- CodeForces 731F Video Cards (数论+暴力)
- Gym 100299C && UVaLive 6582 Magical GCD (暴力+数论)
- UVaLive 6625 Diagrams & Tableaux (状压DP 或者 DFS暴力)
- HDU 4431 Mahjong (DFS,暴力枚举,剪枝)
- 203、【栈与队列】leetcode ——剑指 Offer II 040. 矩阵中最大的矩形 / 85. 最大矩形:暴力+单调栈(C++/Pyhont版本)
- nyoj 66-分数拆分 (Java,暴力)
- 洛谷P1257(暴力超时)