Description 给定a,b,c,求满足方程Ax+By<=C的非负整数解
A,B<=10^9.C<=Min(A,B)*10^9
Solution 【类欧几里得|bzoj2987 Earthquake 类欧几里得】考虑枚举x得到 y≤?C?AxB?y ≤ ? C ? A x B ?
类欧几里得的经典应用，时间太紧了我就先去吃个饭回来再写
回来辣
类欧的几何意义可以看成是求一个梯形内的整点数，不包括纵坐标为0的点，包括边界上的点
先设 f(n,a,b,c)=∑ni=0?ai+bc?f ( n , a , b , c ) = ∑ i = 0 n ? a i + b c ?
若 a≥ca ≥ c 或 b≥cb ≥ c ，那么有
f(n,a,b,c)=(n+1)n2?ac?+(n+1)?bc?+f(n,a%c,b%c,c)f ( n , a , b , c ) = ( n + 1 ) n 2 ? a c ? + ( n + 1 ) ? b c ? + f ( n , a % c , b % c , c )
至于怎么推的可以考虑把前面两项再塞回Σ里面看看
若两个都不满足，那么令 m=?na+bc?m = ? n a + b c ? ，有
f(n,a,b,c)=∑ni=0∑mj=1[j≤?ai+bc?]f ( n , a , b , c ) = ∑ i = 0 n ∑ j = 1 m [ j ≤ ? a i + b c ? ] ，这个可以看成是枚举可行的整点
我们把表达式单独拉出来 j≤?ai+bc?j ≤ ? a i + b c ?
化一下把i单独弄出来得到 i≥?cj+c?b?1a?i ≥ ? c j + c ? b ? 1 a ? ，套进原本的柿子里面，这个就等同于一行一行枚举了
然后有 f(n,a,b,c)=n?m?f(m?1,c,c?b?1,a)f ( n , a , b , c ) = n ? m ? f ( m ? 1 , c , c ? b ? 1 , a )
复杂度分析到处都有我就不贴了
Code
#include
#include
#define rep(i,st,ed) for (int i=st;
i<=ed;
++i)typedef long long LL;
LL solve(LL n,LL a,LL b,LL c) {
if (!c) return 0;
if (a>=c||b>=c) {
return solve(n,a%c,b%c,c)+(a/c)*n*(n+1)/2+(b/c)*(n+1);
} else {
LL m=(n*a+b)/c;
return n*m-solve(m-1,c,c-b-1,a);
}
}int main(void) {
LL a,b,c;
scanf("%lld%lld%lld",&a,&b,&c);
printf("%lld\n", solve(c/a,a,c%a,b)+c/a+1);
return 0;
}推荐阅读
- 个人日记|K8s中Pod生命周期和重启策略
- 学习分享|【C语言函数基础】
- C++|C++浇水装置问题
- 数据结构|C++技巧（用class类实现链表）
- C++|从零开始学C++之基本知识
- 步履拾级杂记|VS2019的各种使用问题及解决方法
- leetcode题解|leetcode#106. 从中序与后序遍历序列构造二叉树
- 动态规划|暴力递归经典问题
- 麦克算法|4指针与队列
- 遇见蓝桥遇见你|小唐开始刷蓝桥（一）2020年第十一届C/C++ B组第二场蓝桥杯省赛真题