标签 - 类欧几里得

? 类欧几里得 ?    2018-12-19 10:49:10    1660    0    0
类欧几里得是统计直线下整点贡献的一种套路,最常见的类欧几里得是求: ∑i=0n⌊ai+bc⌋" role="presentation" style="position: relative;">∑i=0n⌊ai+bc⌋∑i=0n⌊ai+bc⌋ \sum^{n}_{i=0} \left \lfloor \frac{ai+b}{c} \right \rfloor 也就是直线ax+bc" role="presentation" style="position: relative;">ax+bcax+bc\fr
? 解题记录 ? ? BZOJ ? ? 类欧几里得 ?    2018-12-18 18:57:19    374    0    0
题意: 给定a,b,c" role="presentation" style="position: relative;">a,b,ca,b,ca,b,c,求满足方程Ax+By≤C" role="presentation" style="position: relative;">Ax+By≤CAx+By≤CAx+By\le C的非负整数解 A,B≤109,C≤Min(A,B)∗109" role="presentation" style="position: relative;">A,B