[ZZOJ#31]类欧几里得
试题描述
这是一道模板题。
给出 \(a, b, c, n\)，请你求出 \(\sum_{x=0}^n{\lfloor \frac{a \cdot x + b}{c} \rfloor}\)
输入
一行四个正整数 \(a, b, c, n\)。
输出
一个整数表示答案。
输入示例1
10 7 3 3
输出示例1
28
输入示例2
36976101 240442820 735275034 66441189
输出示例2
110998229606855
数据规模及约定
对于 \(50\%\) 的数据，有 \(n \le 10^7\)
对于 \(100\%\) 的数据，保证 \(a, b, c, n \le 10^9\)，答案不会超过 \(9223372036854775807\)（int64 最大值）。
题解
以前出出来的，发现忘记写博客了，来补个坑。
类欧模板。讲解随便就能百度到。
主要思路就是数形结合，将此题转化成“求直线下方整点个数”。对于 \(c \ge a\) 或 \(b \ge a\) 的情况，将整数部分 \(\lfloor \frac{c}{a} \rfloor\) 和 \(\lfloor \frac{b}{a} \rfloor\) 先算出来，再考虑补上没记上的部分，于是将问题变成了 \(b, c < a\) 的情况。对于这个情况，就是求一个直角梯形内部整点个数（这个直角梯形 \(y\) 轴上结局和斜率都小于 \(1\) 的性质保证后面的子问题规模会缩小），我们考虑不按 \(x\) 坐标枚举，变成按 \(y\) 坐标枚举，推一推式子发现能转化成子问题。
#include#include #include #include #include #include using namespace std;#define rep(i, s, t) for(int i = (s); i <= (t); i++)#define dwn(i, s, t) for(int i = (s); i >= (t); i--)int read() { int x = 0, f = 1; char c = getchar(); while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); } while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); } return x * f;}#define LL long longLL solve(LL a, LL b, LL c, LL n) { if(!n) return b / c; if(n < 0) return 0; if(a >= c || b >= c) return b / c * (n + 1) + a / c * n * (n + 1) / 2 + solve(a % c, b % c, c, n); LL m = (a * n + b) / c; return n * m + m - solve(c, a - b + c - 1, a, m - 1);}int main() { int a = read(), b = read(), c = read(), n = read(); printf("%lld\n", solve(a, b, c, n)); return 0;}