Gym 101334J 找规律
2024-10-19 09:48:55
题意:
给出正整数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
分析:
K对根号k之后的值取模会有相同的商出现,且具有相同的商的余数呈等差数列。
#include <bits/stdc++.h>
using namespace std; typedef long long ll; int main()
{
freopen("joseph.in","r",stdin);
freopen("joseph.out","w",stdout);
ll n,k;
while(~scanf("%I64d%I64d",&n,&k))
{
ll sum=0;
if(n>k) sum+=(n-k)*k;
ll q=sqrt(1.0*k);
ll p=k/q;
for(int i=1;i<=n && i<=p;i++)
sum+=k%i;
for(int i=q;i>1;i--)
{
ll p1=k/i;
ll p2=k/(i-1);
if(p1>n) break;
if(p2>n) p2=n;
sum+=(k%(p1+1)+k%p2)*(p2-p1)/2;
}
printf("%I64d\n",sum);
}
return 0;
}
最新文章
- javascript随笔20160808
- IBM x3850 x5 服务器 安装 Windows Server 2008
- With语句以及@contextmanager的语法解析
- Deep Learning 11_深度学习UFLDL教程:数据预处理(斯坦福大学深度学习教程)
- 【转】beancopy的替代方案
- .Net字符串驻留池
- C++中 类的构造函数理解(一)
- Beginning OpenGL ES 2.0 with GLKit Part 1
- emctl start dbconsole OC4J_dbconsole*** not found
- java String分类trim,substring,replaceAll,indexOf使用功能
- Ubuntu加上一个命令搜索路径/etc/ environment
- Mvc Swagger报错的解决办法。
- ,vue-router使用心得
- 不偏移的天地图地图服务-SuperMap版
- python中lambda的用法
- mysql 不同引擎的比较
- java自定义事件机制分析
- 170526、spring 执行定时任务
- 转 group_concat函数详解
- 【Linux】head命令