题解【[BJOI2012]算不出的等式】
题目背景emmm
\[\text{首先特判掉p=q时的情况(ans = }p^2-1\text{)}\]
\[\text{构造函数}f(k) = \left\lfloor \frac{kq}{p}\right\rfloor\]
\[\text{考虑这个函数}g(x)=\left\lfloor x \right\rfloor\text{的几何意义}\]
\[\text{他表示在平面直角坐标系中,横坐标为定值,纵坐标小于等于x的整点个数}\]
\[\text{好,那么我们继续来看f(k),他表示所有横坐标为定值,纵坐标小于等于}\frac{kp}{q}\text{的数的个数}\]
\[\text{那么构造}t(k)=\frac{kq}{p}\text{,那么}\sum_{i=1}^{\frac{p-1}{2}}f(k)\text{的几何意义是:}\]
\[\text{所有横坐标}\in(1,\frac{p-1}{2})\;\text{的整数,纵坐标是整数的点数}\]
即
中蓝线以下部分中整点数
~
\[\text{又因为}\left\lfloor t(k) \right\rfloor_{max} = \frac{q-1}{2}\]
\[\text{所有只用考虑纵坐标在直线}\{(0,0),(\frac{p-1}{2},\frac{q-1}{2})\}\text{以下的整点}\]
\[\text{然后p,q互换同理}\]
\[\text{所以就是长方形ABCD}(A(0,0),B(0,\frac{p-1}{2}),C(\frac{q-1}{2},\frac{p-1}{2}),D(\frac{q-1}{2},0)\text{中整点个数}\]
\[\text{所以答案就是}\frac{(p-1)\times(q-1)}{4}\]
然后你就切了这道蓝题~
最新文章
- 埃尔米特插值问题——用Python进行数值计算
- mysql索引总结----mysql 索引类型以及创建
- Tabbed Activity的使用(Fragment)
- Linux open函数
- 复选框全选、全不选和反选的效果实现VIEW:1592
- ORACLE DG之参数详解
- Chrysler -- CCD (Chrysler Collision Detection) Data Bus
- Hive JSON数据处理的一点探索
- 错误: 无法找到或可以不被加载到主类 Main
- nRF51800 蓝牙学习 进程记录 2:关于二维数组 执念执战
- 福利:Axure 8.0 Pro 破解版下载
- Java内存分配以及GC
- 学习笔记(node.js)
- sql 中取整,四舍五入取整,向下取整,向上取整。
- FPGA 中三角函数的实现
- Ubuntu 中卸载软件的几种命令
- 关于微信支付接口,curl错误代码58
- Vue图片懒加载
- shell 获取脚本的绝对路径
- 将h264和aac码流合成flv文件
热门文章
- 51nod 1206:Picture 求覆盖周长
- C++ Socket WSAENOBUFS WSAoverlapped
- asp.net mvc3用file上传文件大小限制问题
- CentOS7 静默安装Oracle XE 11g
- Sass - &;引用父选择器
- [ cocos2d-JS ] 创建项目命令
- 找不到xml、找不到类
- 如何为 .NET Core 安装本地化的 IntelliSense 文件
- webapi------宿主程序
- torch.utils.data.DataLoader 将数据按批次分成很多组,每次抛出一个小组