【题解】CQOI2007余数求和
2024-08-28 13:27:46
大家都说这题水然而我好像还是调了有一会儿……不过暴力真的很良心,裸的暴力竟然还有60分。
打一张表出来,就会发现数据好像哪里有规律的样子,再仔细看一看,就会发现k/3~k/2为公差为2的等差数列,k/2~之后为公差为1的等差数列,于是我们就可以利用高斯求和快速求解啦。自认为代码是能够看得的...
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define int long long
LL ans;
int p, x = , n, m, k, base, skipper; LL Get_sum()//高斯求和,从p项开始公差为x
{
int y = x - ;
int base = (k % p);
int end = max(base % y, base - (m - p) * y);
skipper = ((base - end) / y) + ;
return ((LL)(base + end) * (LL)skipper) >> ;
} void init()//分段设x值
{
if(k > ) x = ;
else if(k > ) x = ;
else if(k > ) x = ;
else if(k > ) x = ;
else x = ;
} signed main()
{
scanf("%lld%lld", &n, &k);
m = min(n, k);
init();
for(p = ; p <= m; p ++)
{
if(p == (k / x) + )
{
ans += Get_sum();
p += (skipper - );//统计加了多少项
x -= ;
}
else ans += (k % p);
}
if(n > k) ans += (LL) (n - k) * (LL) (k);
printf("%lld", ans);
return ;
}
最新文章
- Android自定义控件----RadioGroup实现APP首页底部Tab的切换
- Java经典实例:使用正则表达式:测试模式
- php 设计模式 - 单例
- Activity使用Dialog样式导致点击空白处自动关闭的问题
- C语言内存分配函数
- Android Sip学习(三)Android Voip实现
- 实现ie6下的居中
- 如何通过 WebP 自适应方案减少图片资源大小
- NOIP-比例简化
- BZOJ-9-3295: [Cqoi2011]动态逆序对
- jdk1.8新特性总结
- [PDFBox]后台操作pdf的工具类
- stylus笔记(三)
- Android Fragment的使用(转载)
- hdu 2874 Connections between cities(st&;rmq LCA)
- cat /proc/iomem
- 【转】社区O2O的增量与存量,机会在哪?
- AutoHotkey的函数对象的Bind方法绑定参数的应用
- document的属性与方法小结
- [Functional Programming] Draw Items from One JavaScript Array to Another using a Pair ADT
热门文章
- 【ospf-链路验证】
- 09 mongoDB基础(进阶)
- python函数的返回值
- 【Leetcode】647. Palindromic Substrings
- python2.7练习小例子(十九)
- asp.net 模拟CURL调用微信公共平台API 上传下载多媒体文件接口
- [电子书] 《Android编程兵书》PDF
- 让webapi支持CORS,可以跨域访问
- 使用testng.xml组织测试用例
- MySQL☞between ... and ...