[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{a} \rfloor\) 先算出來，再考慮補上沒記上的部分，于是將問題變成了 \(b, c < a\) 的情況。對于這個情況，就是求一個直角梯形內部整點個數（這個直角梯形 \(y\) 軸上結局和斜率都小于 \(1\) 的性質保證后面的子問題規模會縮小），我們考慮不按 \(x\) 坐標枚舉，變成按 \(y\) 坐標枚舉，推一推式子發現能轉化成子問題。

#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <algorithm> 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; }

轉載于:https://www.cnblogs.com/xiao-ju-ruo-xjr/p/8005645.html

總結

以上是生活随笔為你收集整理的[ZZOJ#31]类欧几里得的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。