BZOJ1257 [CQOI2007]余数之和[规律]
2024-10-07 01:03:58
被zcr和yy轮流嘲讽了一番,感觉自己智商日渐下降。。。\TヘTツ
先拆mod变成整数除法,然后就是$nk- \Sigma_{i=1}^{n} i * \lfloor \frac{k}{i} \rfloor$。求后面那个。
然后发现$\lfloor \frac{k}{i} \rfloor$是连续且单调不增的。对于$x$,$[x,\lfloor \frac{k}{\lfloor \frac{k}{i} \rfloor} \rfloor]$内这个商是一样的。可以意会。
这个是找规律得到的,不会证QWQ。于是每一小段一样的商乘以这一段的每一个$i$累加。
复杂度是在$i \leq \sqrt{k}$时有$\sqrt{k}$种商。$i \geq \sqrt{k}$时的商小于$\sqrt{k}$,也最多$\sqrt{k}$种。于是复杂度是根号的。
WA:关于longlong的事以及每次区间右端点要判是否超过$n$。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
template<typename T>inline T _min(T A,T B){return A<B?A:B;}
template<typename T>inline T read(T&x){
x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;
while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;
}
inline ll sum(ll i,ll j){return (i+j)*(j-i+)/;}
ll ans,n,k; int main(){//freopen("test.in","r",stdin);//freopen("test.out","w",stdout);
read(n),read(k);ans=n*k;(n>k)&&(n=k);
for(register ll i=,r=;i<=n;i=r+)ans-=sum(i,r=_min(n,k/(k/i)))*(k/i);
return printf("%lld\n",ans),;
}
最新文章
- Python类中super()和__init__()的关系
- C# 调用一个按钮的Click事件(利用反射)
- 【CodeForces 672B】Different is Good
- meta标签详解(meta标签的作用)///////////////////////////转
- Android四大组件之Activity(活动)及其布局的创建与加载布局
- C#基础总结之五Dictionary<;string, string[]>;和while循环
- Reverse Integer [LeetCode]
- xy
- WebForm中如何防止页面刷新,后退导致的重复提交
- 关于call 与 apply 那些事
- Java眼中的XML文件写入
- (NO.00005)iOS实现炸弹人游戏(四):游戏数据的初始化(一)
- 关于Java的散列桶, 以及附上一个案例-重写map集合
- 在HyperLedger Fabric中启用CouchDB作为State Database
- Android-shape圆形&;转圈圈
- swift面向协议编程
- istio 服务地图
- DJANGO ADMIN 一些有用的设置(转)
- SVG渲染顺序及z轴显示问题(zIndex)
- 富文本存储型XSS的模糊测试之道