Rockdu's Blog
“Where there is will, there is a way”
亲 您的浏览器不支持html5的audio标签
Toggle navigation
Rockdu's Blog
主页
数据结构
字符串算法
图论
数论、数学
动态规划
基础算法
[其它内容]
计算几何
科研笔记
归档
标签
BZOJ 2987：Earthquake
? 解题记录 ?
? BZOJ ?
? 类欧几里得 ?
2018-12-18 18:57:19
395
0
0
rockdu
? 解题记录 ?
? BZOJ ?
? 类欧几里得 ?
### 题意： 给定$a,b,c$,求满足方程$Ax+By\le C$的非负整数解 $A,B≤10^9,C≤Min(A,B)*10^9$ ### 题解： 题目相当于求： $$\sum^{\lfloor \frac{C}{A} \rfloor}_{i=0} \left \lfloor \frac{-Ai+C}{B} \right \rfloor$$ 不难发现，我们操作一下就行了，用$\lfloor \frac{C}{A} \rfloor - i$换$i$，转化为： $$\sum^{\lfloor \frac{C}{A} \rfloor}_{i=0} \left \lfloor \frac{C\%A+Ai}{B} \right \rfloor$$ 这个转化也可以通过画图发现。 那么问题变成了最开始的问题：如何求 $$\sum^{n}_{i=0} \left \lfloor \frac{ai+b}{c} \right \rfloor$$ 直接类欧几里得就可以了 代码很简短 类欧几里得可以看一篇很好的博客： [我是"很好的博客"，点我](http://blog.leanote.com/post/rockdu/TX22) ``` #include<cstdio> #define LL long long using namespace std; LL a, b, c, n; LL f(LL a, LL b, LL c, LL n) { if(c == 0) return 0; if(a >= c || b >= c) { return (a / c) * n * (n + 1) / 2 + (b / c) * (n + 1) + f(a % c, b % c, c, n); } LL fn = (1ll * a * n + b) / c; LL ret = f(c, c - b - 1, a, fn - 1); return 1ll * n * fn - ret; } int main() { scanf("%lld%lld%lld", &a, &b, &c); printf("%lld", f(a, c % a, b, c / a) + c / a + 1); return 0; } ```
上一篇:
类欧几里得算法入门
下一篇:
LOJ #6433. 「PKUSC2018」最大前缀和
0
赞
395 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
文档导航
rockdu
Rockdu's Blog
没有帐号? 立即注册