Openjudge NOI题库数论185 反正切函数的应用

本是古典何须时尚 2021-09-29 09:40 231阅读 0赞

**Openjudge-185反正切函数的应用**

185:反正切函数的应用 总时间限制: 1000ms 内存限制: 65536kB 描述 反正切函数可展开成无穷级数，有如下公式 (其中0 <= x <= 1) 公式(1) 使用反正切函数计算PI是一种常用的方法。例如，最简单的计算PI的方法： PI=4arctan(1)=4(1-1/3+1/5-1/7+1/9-1/11+...) 公式(2) 然而，这种方法的效率很低，但我们可以根据角度和的正切函数公式： tan(a+b)=[tan(a)+tan(b)]/[1-tan(a)*tan(b)] 公式(3) 通过简单的变换得到： arctan(p)+arctan(q)=arctan[(p+q)/(1-pq)] 公式(4) 利用这个公式，令p=1/2,q=1/3，则(p+q)/(1-pq)=1，有 arctan(1/2)+arctan(1/3)=arctan[(1/2+1/3)/(1-1/2*1/3)]=arctan(1) 使用1/2和1/3的反正切来计算arctan(1)，速度就快多了。 我们将公式(4)写成如下形式 arctan(1/a)=arctan(1/b)+arctan(1/c) 其中a,b和c均为正整数。 我们的问题是：对于每一个给定的a（1 <= a <= 60000），求b＋c的值。我们保证对于任意的a都存在整数解。如果有多个解，要求你给出b+c最小的解。 输入 输入文件中只有一个正整数a，其中 1 <= a <= 60000。 输出 输出文件中只有一个整数，为 b+c 的值。 样例输入 1 样例输出 5

题意：对于每一个给定的a（1 <= a <= 60000），保证存在整数解b,c满足：

p=1/b

q=1/c

r=(p+q)/(1-pq)=1/a

求整数b,c且输出最小的b+c。

过程：

数论分析——

/\*

目标1）——题目问b+c，我们就把b+c表示出来

\*/

经整理，

r的分子：(p+q)=1/b + 1/c=(b+c)/bc

r的分母：(1-pq)=1 - 1/bc=(bc-1)/bc

r=(p+q)/(1-pq)=(b+c)/(bc-1)

a=1/r=(bc-1)/(b+c)

b+c=(bc-1)/a①

题目要求b+c最小整数解，

即求整数b,c使得bc-1|a并且bc-1最小。②

此时尝试从信息学角度考虑，我们的算法将枚举b,c以满足上述条件，

但是双变量的枚举将造成O(n^2)的时间复杂度，我们希望减少一个枚举量

所以——

目标2）——尝试减少一个枚举量，如将b移动至等号一边

a(b+c)=bc-1

ab+ac=bc-1

ac+1=bc-ab

b=(ac+1)/(c-a)①

——嘿嘿，只需要枚举c即可

又因为b,c为正整数，即b,c > 0，

所以枚举整数c，  只要c满足：使得b是个整数，取b+c最小值即可。

来来来，我们确定一下枚举范围：

其中c1使得。。。。。

c2使得。。。。。

Oh!!Oh!!Oh！！！

出事故了！！

在递减枚举c的时候，b的单调性不明朗，c的枚举范围怎么确定呀？！

原因就在：①式等号右边，分子分母都存在枚举量，影响单调性

所以——

目标3）——将①式等号右边的枚举量统一放在 分子or分母 处

这时候我们将用到枚举中一个非常重要的技巧——改变枚举量

因为c>a

我们惊奇的发现①中分母为（c-a），

直觉告诉我们只需要设c=a+x，分母就是(c-a)=(a+x-a)=x，目标三就达成啦\*^ ~ ^\*

于是令c=a+x，

①　　==>   b=(aa+ax+1)/x=a+(aa+1)/x

哇，多么美妙的单调减函数呀~

故，枚举x from aa+1 to 1

满足x使得b是个整数，立即输出吧~

代码时间复杂度O(a^2)

算法分析结束！！Conguatulations~~

代码建立——emm还没来得及写代码……

转载于:https://www.cnblogs.com/CXSheng/p/7449499.html

发表评论取消回复

表情：

评论列表（有 0 条评论，231人围观）

还没有评论，来说两句吧...

相关阅读

相关激活函数 ReLU、sigmoid、tanh（双曲正切）

![20191009191333910.png][][个人主页 ][Link 1] -------------------- ![watermark_type_ZmFu

叁歲伎倆/ 2023年06月17日 07:54/ 0 赞/ 16 阅读

相关 matlab 求向量的正切,matlab中的反正切函數 | 學步園

Matlab 中求相位的函數有 phase atan2 angle atan Phase和angle的區別： 1Phase 支持標量和一維向量輸入 angle 可以輸

浅浅的花香味﹌/ 2023年01月15日 08:18/ 0 赞/ 143 阅读

相关计算机应用基础的题库,计算机应用基础题库

《计算机应用基础题库》由会员分享，可在线阅读，更多相关《计算机应用基础题库(26页珍藏版)》请在人人文库网上搜索。 1、计算机应用基础样题,交卷并查看成绩,单选题,多选题,综

矫情吗；*/ 2022年10月19日 12:54/ 0 赞/ 301 阅读

相关 C语言中两个反正切函数atan与atan2的区别

我们可以使用正切操作将角度转变为斜率,那么怎样利用斜率来转换为角度呢?可以利用斜率的反正切函数将他转换为相应的角度.as中有两个函数可以计算反正切,我们来看一下.

布满荆棘的人生/ 2022年09月23日 13:58/ 0 赞/ 166 阅读

相关反正切三角函数的c源代码

某些场合，如游戏开发，工程计算中，可能需要计算反三角函数，下面是计算反正切三角函数的c源代码实例： atan\_self(double x) \{ //atan(x)=x-x

亦凉/ 2022年08月08日 17:36/ 0 赞/ 197 阅读

相关 OpenJudge

总时间限制: 1000ms 内存限制: 65536kB 描述某程序员开始工作，年薪N万，他希望在中关村公馆买一套60平米的房子，现在价格是200万，假设房子价格以每

小灰灰/ 2022年07月15日 09:52/ 0 赞/ 219 阅读

相关计算机网络应用层题库

免费版：[华文慕课计算机网络应用层课后题][Link 1] 网络课课后题 1 P2P模式的最主要特点是：要安装客户端程序但没有固定服务器 2 P2P架构下分发一个

约定不等于承诺〃/ 2022年05月18日 07:36/ 0 赞/ 270 阅读

相关 OpenJudge-合格的字符串

OpenJudge-合格的字符串 -------------------- 题目链接：[1:合格的字符串][1] 代码： include<iostre

深藏阁楼爱情的钟/ 2022年05月15日 12:11/ 0 赞/ 186 阅读

相关正弦、余弦和正切

[https://www.shuxuele.com/sine-cosine-tangent.html][https_www.shuxuele.com_sine-cosine-t

傷城~/ 2021年11月05日 12:48/ 0 赞/ 708 阅读

相关 Openjudge NOI题库数论185 反正切函数的应用

Openjudge-185反正切函数的应用 185:反正切函数的应用总时间限制: 1000ms 内存限制: 65536kB 描述反正切函数可展开成无穷级数，有如下

本是古典何须时尚/ 2021年09月29日 09:40/ 0 赞/ 232 阅读