51Nod 1225 余数之和 —— 分区枚举
2024-09-07 17:15:23
题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1225
F(n) = (n % 1) + (n % 2) + (n % 3) + ...... (n % n)。其中%表示Mod,也就是余数。
例如F(6) = 6 % 1 + 6 % 2 + 6 % 3 + 6 % 4 + 6 % 5 + 6 % 6 = 0 + 0 + 0 + 2 + 1 + 0 = 3。
给出n,计算F(n), 由于结果很大,输出Mod 1000000007的结果即可。
Input
输入1个数N(2 <= N <= 10^12)。
Output
输出F(n) Mod 1000000007的结果。
Input示例
6
Output示例
3
题解:
这题(LightOJ1245)的加强版,本来是求sigma(n/i) 1<=i<=n,而此题求的是:sigma(n%i) 1<=i<=n。
分两个区间枚举:
第一个区间 [1,sqrt(n)]:设i为除数,从1到sqrt(n)枚举i, 直接 ans += n%i;
第二个区间 [sqrt(n), n]:设i为商,从1到sqrt(n)枚举i,由于用后面区间的数去除n所得到的商,在很大一片区域是相同的,在这片区域,他们的余数成等差数列,且公差即为商,所以就可根据等差数列的求和公式,求出这段区域的余数和了。
需要特判在sqrt(n)处是否重复计算了。
代码如下:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
using namespace std;
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
const int MOD = 1e9+;
const int MAXM = 1e5+;
const int MAXN = 1e6+; //inv(2,MOD-2) = 500000004
int main()
{
LL n;
while(scanf("%lld", &n)!=EOF)
{
LL m = (LL)sqrt(n);
LL ans = ;
for(LL i = ; i<=m; i++)
ans = (ans+n%i)%MOD;
for(LL i = ; i<=m; i++)
{
LL cnt = ((n/i)%MOD-(n/(i+))%MOD+MOD)%MOD; //求个数也要求模
LL a1 = n%i;
LL s = (a1*cnt%MOD + ((cnt*(cnt-)%MOD)*500000004LL%MOD)*i%MOD)%MOD;
ans = (ans+s)%MOD;
} if(n/m==m) ans = (ans-(n%m)+MOD)%MOD;
printf("%lld\n",ans);
}
}
最新文章
- 《Java4Android》视频学习笔记——抽象类和抽象函数
- 调试2440 RAM拷贝至SDRAM遇到的问题
- [LintCode] Kth Smallest Number in Sorted Matrix 有序矩阵中第K小的数字
- C++ Pirmer : 第十四章 : 重载运算符与类型转换之函数调用运算符与标准库的定义的函数对象
- Regional Changchun Online--Travel(最小生成树&;&; 并查集)
- Mac下如何显示隐藏文件/文件夹_百度经验
- int string convert
- SET STATISTICS IO和SET STATISTICS TIME 在SQL Server查询性能优化中的作用
- android媒体--图库与API层MediaPlayer的交互
- SQL-PL/SQL基础
- 前后端分离djangorestframework—— 在线视频平台接入第三方加密防盗录视频
- JVM GC机制
- mac系统 pip3 install scrapy 失败 No local packages or working download links found for incremental>;=16.10.1
- Effective Java -- 使可变性最小化
- 在 Web 页面中使用离线地图
- php5.4使用dblib扩展,连接sqlserver中文乱码问题
- js实现的map方法
- gradlew 的https代理设定
- java CyclicBarrier以及和CountDownLatch的区别
- 用UIControl封装Button