LuoguP7127 「RdOI R1」一次函数(function) 题解
Content
设 \(S_k\) 为直线 \(f(x)=kx+k-1\),直线 \(f(x)=(k+1)x+k\) 与 \(x\) 轴围成的三角形的面积。现在给出 \(t\) 组询问,每组询问给定一个整数 \(n\),求 \(\sum\limits_{i=1}^n S_i\)。结果用分数表示。
数据范围:\(1\leqslant t\leqslant 2\times 10^6.0\leqslant n\leqslant 2\times 10^6\)。
Solution
很简单的一道找规律题目。
我们发现,形如 \(f(x)=kx+k-1\) 的直线都会经过 \((-1,-1)\) 这个点。我们再稍微画几个图就能够发现,题目所要求的东西,无非就是以 \((0,0),(-1,-1)\) 以及最后一个 \(S_i\),也就是 \(S_n\),被约束的后一条直线 \(f(x)=(n+1)x+n\) 与 \(x\) 轴的点为三个顶点的三角形的面积罢了。而且很容易发现,我们的三角形如果以在 \(x\) 轴上的边为底边的话,它的高自然就是 \(1\)。再说,这条 \(x\) 轴上的边也很容易求出来:只需要求 \(f(x)=(n+1)x+n\) 这条直线与 \(x\) 轴的交点,再取个绝对值就好了。我们很容易求出上面所说的那条直线与 \(x\) 的交点为 \((-\dfrac{n}{n+1},0)\)。所以那条底边的长度就是 \(\dfrac{n}{n+1}\)。
因此,这道题目的答案,也就是 \(\sum\limits_{i=1}^nS_i=\begin{cases}0&n=0\\\dfrac{n}{2(n+1)}&n>0\end{cases}\)。注意:
- \(n=0\) 的时候,显然无法构成一个三角形,因此面积为 \(0\)。
- 注意约分,直接将分子和分母同时除以它们的最大公约数(也就是 \(\gcd\{n,2(n+1)\}\))就好。
只是一时兴起想做道题目,不意味着正式回归。
但是,请等着我。(本文章原文写于 2020 年 12 月 27 日——笔者注)
Code
请注意 \(\textsf{NOI}\) 系列赛事不支持 algorithm 库的 __gcd
函数。建议自己写个 gcd 函数,反正又不难,对吧?
什么,要 gcd 函数?下面:
int gcd(int a, int b) {return !b ? a : gcd(b, a % b);} //数据类型根据实际情况适当调整
下面的是正式的代码,注意直接拿这个代码编译是不会通过的。
#include <bits/stdc++.h>
using namespace std;
int t, n;
int main() {
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
if(!n) puts("0");
else printf("%d/%d\n", n / gcd(n, 2 * (n + 1)), 2 * (n + 1) / gcd(n, 2 * (n + 1)));
}
return 0;
}
最新文章
- OC KVC
- Visual Studio 2015中快捷键总结
- wpf listview 换行
- Android屏幕旋转总结
- EntityFramework Core 学习笔记 —— 创建模型
- ckeditor的详细配置
- Linux shell 脚本小记
- 对进度条progressbar的调整
- iOS 视图调试器(Debug View Hierarchy) 之 初试牛刀
- C# 启动 SQL Server 服务
- 自己编译Android(小米5)内核并刷入(一键自动编译打包)
- 二叉查找树的C++实现
- go 的匿名函数和闭包
- Qt编写调试日志输出类带网络转发(开源)
- SpringBoot读取application.properties文件内容
- Django popup示例
- DOM节点树和元素树--深度遍历
- js中两种定时器的设置及清除
- 【源码学习之spark streaming 1.6.1 】
- Apache Kafka源码分析 &ndash; Controller