类欧几里得是统计直线下整点贡献的一种套路，最常见的类欧几里得是求：
∑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
题意：
给定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
Rockdu's Blog