企业官网建设流程全解析

原题链接：

Problem - 2260B - Codeforces

CF2260B Monocarp and Projects - 洛谷

我的解答：

递归+优化

#include<iostream> using namespace std; long long find(long long x, long long y, long long k) { long long ans = 0; if (k == 1) return y % x; if (y < 2 * x) return (y - x) * k; else { ans += y % x; ans += find(++x, ++y, --k); return ans; } } int main() { long long t, x, y, k; cin >> t; for (int i = 0; i < t; i++) { cin >> x >> y >> k; cout << find(x, y, k) << endl; } return 0; }

本质就是求（y + i）%(x + i) 的累加和

0 <= i <= k

基线条件：当k = 1时 直接返回当前计算结果，不进行下一次递归。

否则就记录当前y % x

然后对 ++y，++x，--k进行下一次递归，这里的k相当于次数了。

不过就这么完结了，肯定会TLE——毕竟k可以高达10^12

可以注意到

如果此时

y < 2*x 也就是商是1的时候

不管以后两边同时＋1多少次，商还是1

余数始终是

（y +i） - （x+i);

也就是

y - x;

为什么？

y + t < 2*(x + t)

等价于

y < 2*x + t

t ≥ 0

始终成立；

所以就省去了后边的递归

同时别忘了累加剩余的次数k；

最佳解答：

#include <iostream> using namespace std; int main() { int t; cin >> t; while (t--) { long long x, y, k; cin >> x >> y >> k; long long ans = 0, i = 0; // 前段：商 >= 2，即 y+i >= 2*(x+i)，余数逐个在变，只能枚举 while (i < k && y + i >= 2 * (x + i)) { ans += (y + i) % (x + i); i++; } // 后段：商 == 1，余数恒等于 y - x，一步算完 ans += (k - i) * (y - x); cout << ans << '\n'; } return 0; }

思路差不多，只不过是用的循环方式写的