BZOJ-2987 Earthquake(类欧几里得算法)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了BZOJ-2987 Earthquake(类欧几里得算法)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1556字，纯文字阅读大概需要3分钟。

内容图文

题目描述

??给定 \(A,B,C\)，求满足方程 \(Ax+By\leq C\) 的 非负 整数解 \((x,y)\)（\(A,B\leq 10^9,C\leq \min(A,B)\times 10^9\)）。

分析

??考虑枚举 \(y\)，移项得：\(0\leq y\leq \lfloor\frac{C-Ax}{B}\rfloor\)，当 $ x=0$ 时，\(y\) 枚举的上界为 \(\lfloor\frac{C}{A}\rfloor\)。

??这相当于求线段 \(y=\frac{C-Ax}{B}(0\leq y\leq \lfloor\frac{C}{A}\rfloor)\) 在第一象限和 \(x,y\) 正半轴内整点的数量。

??把斜率为负调整成斜率为正的线段，原来线段的两端点为 \((0,\frac{C}{B}),(\lfloor\frac{C}{A}\rfloor,\frac{C-A\lfloor\frac{C}{A}\rfloor}{B})\)，将两端点对换，分别为 \((0,\frac{C-A\lfloor\frac{C}{A}\rfloor}{B}),(\lfloor\frac{C}{A}\rfloor,\frac{C}{B})\)，此时线段为 \(y=\frac{A}{B}x+\frac{C-A\lfloor\frac{C}{A}\rfloor}{B}=\frac{Ax+C\% A}{B}\)。

??问题即求（加 \(1\) 是因为 \(x=0\) 时也是合法解）：

\[\sum_{i=0}^{\lfloor\frac{C}{A}\rfloor}\Big(\Big\lfloor\frac{Ax+C\%A}{B}\Big\rfloor+1\Big)=\sum_{x=0}^{\lfloor\frac{C}{A}\rfloor}\Big(\Big\lfloor\frac{Ax+C\%A+B}{B}\Big\rfloor\Big) \]

??考虑一个一般性问题：

\[f(a,b,c,n)=\sum_{i=0}^{n}\Big\lfloor\frac{ai+b}{c}\Big\rfloor \]

??\(1.\) 当 \(a\geq c\) 或 \(b\geq c\) 时，

??\(2.\) 当 \(a<c\) 且 \(b<c\) 时，

??可以发现右边递归成为子问题，继续一轮操作即可。边界条件：\(a=0\)。

代码

#include<bits/stdc++.h>
using namespace std;
long long A,B,C;
long long solve(long long a,long long b,long long c,long long n)
{
    if(a==0)
        return (n+1)*(b/c);
    if(a>=c||b>=c)
        return solve(a%c,b%c,c,n)+(a/c)*n*(n+1)/2+(b/c)*(n+1);
    long long m=(a*n+b)/c;
    return n*m-solve(c,c-b-1,a,m-1);
}
int main()
{
    cin>>A>>B>>C;
    cout<<solve(A,C%A+B,B,C/A)<<endl;
    return 0;
}

内容总结

以上是互联网集市为您收集整理的BZOJ-2987 Earthquake(类欧几里得算法)全部内容，希望文章能够帮你解决BZOJ-2987 Earthquake(类欧几里得算法)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---