codevs2190 有理逼近

2023-11-07 20:48
文章标签 逼近 有理 codevs2190

本文主要是介绍codevs2190 有理逼近,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述 Description

对于一个素数P,我们可以用一系列有理分数(分子、分母都是不大于N的自然数)来逼近sqrt(p),例如P=2,N=5的时候:1/1<5/4<4/3< sqrt(2)<3/2<5/3<2/1。
任 务 :
给定P、N(N>sqrt(p)),求X、Y、U、V,使x/y< sqrt(p)< u/v且x/y与sqrt(p)之间、sqrt(p)与u/v之间都不能再插入满足题意的有理分数。
输入描述 Input Description

输入文件的第一行为P、N 输出描述 Output Description

输出文件只有一行,格式为“X/Y U/V”。注意,答案必须是既约的,也就是说分子、分母的最大公约数必须等于1。

枚举分母,对于这个分母找到最接近的分子,二分查找。

#include<cstdio>
#include<cstring>
#define LL long long
int gcd(int x,int y)
{return y?gcd(y,x%y):x;
}
int main()
{int i,j,k,m,n,p,q,x,y,z,l,r,mid,la=-1,lb,ua=-1,ub;scanf("%d%d",&p,&n);for (i=1;i<=n;i++){l=1;r=n;while (l<=r){mid=(l+r)/2;if (mid*mid>(LL)p*i*i){if (gcd(i,mid)==1&&(ua==-1||mid*ua<i*ub)){ua=i;ub=mid;}r=mid-1;}else{if (gcd(i,mid)==1&&(la==-1||mid*la>i*lb)){la=i;lb=mid;}l=mid+1;}}}printf("%d/%d %d/%d\n",lb,la,ub,ua);
}

这篇关于codevs2190 有理逼近的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/366193

相关文章

超强台风摩羯逼近!或成大陆史上最强登陆台风,防御措施需到位

超强台风摩羯逼近!或成大陆史上最强登陆台风,防御措施需到位 摩羯即将登录,各位兄弟姐妹注意安全!#大型纪录片#摩羯#台风 推荐阅读: 一夜蒸发2万亿!英伟达市值遭遇滑铁卢 《火速围观!黑神话悟空IP山西空心月饼,又一波抢购热潮即将来袭》 直击心灵!佤写不来情歌,却意外火爆全网,你听了没? 警告!明年6至9月假期空窗期,你的旅行计划何去何从? 独家揭秘!雷军豪赠《黑神话:悟空》给王腾,

研之有理—记2017年考研

10月份实习回来,就开启了考研的征程。伴随着昨天的返程,2017年的考研画上了句号。 一,形势分析   今年不再像过去的考试一样,今年的考试在职研究生和其他人统一考试,考试科目也相同。而且是第一年,录取政策等谁也说不清楚。所以对我来说,是一次不小的挑战,同时我学习是文科,大学四年都没有学习数学了,突然知道要学习高数,心中还是有点忐忑。所以总体来说,挑战不小。 二,考试准备中    第一个阶段

【凸优化】连续凸逼近

文章目录 1-理论2-实践 1-理论 连续凸逼近(Successive Convex Approximation, SCA)是一种用于解决非凸优化问题的常用方法。它通过将原始非凸问题分解为一系列凸子问题来求解,每个子问题都是在上一步的解的基础上构造的,逐步逼近全局最优解。以下是连续凸逼近的一般求解过程: 问题描述 设有一个非凸优化问题,其形式如下: min ⁡ x   f

从函数逼近角度理解神经网络、残差连接与激活函数

概述 最近思考激活函数的时候,突然想到神经网络中残差连接是不是和函数的泰勒展开很像,尤其是在激活函数 f ( x ) = x 2 f(x)=x^2 f(x)=x2时(这个激活函数想法来源于 f ( x ) = R e L U 2 ( x ) [ 3 ] f(x)=ReLU^2(x)[3] f(x)=ReLU2(x)[3]),所以验证了一下就顺便写下来了,本文抛砖引玉,如果有建议或更好的想法可以写

有理B样条曲线曲面(NURBS)--拟合技术

非有理B样条曲线曲面(NURBS) 1.NURBS曲线 NURBS(Non-Uniform Rational B-Spline)曲线是一种在计算机辅助设计(CAD)和计算机图形学中广泛使用的数学表示方法,用于精确地定义和渲染复杂的曲线和曲面。NURBS曲线结合了B-Spline曲线和Bezier曲线的优点,提供了对曲线形状的精确控制以及对曲线几何和拓扑属性的灵活操作。 1.1.NURBS曲线

OpenCV轮廓、多边形逼近、关键点、周长和面积、边界框、矩、轮廓树、凹凸包、几何直方图、匹配

1.轮廓的多边形逼近  2.轮廓的关键点  3.轮廓的周长和面积  4.轮廓的边界框  5.轮廓的矩  6.轮廓的轮廓树   7.轮廓的凸包和凸缺陷  8.轮廓的成对几何直方图   9.轮廓的匹配    轮廓的特性: 1.轮廓的多边形逼近     轮廓的多边形逼近指的是:使用多边形来近似表示一个轮廓。     多边形逼近的目的是为了减少轮

函数逼近问题

http://baike.so.com/doc/6449832.html 函数论的一个重要组成部分,涉及的基本问题是函数的近似表示问题。在数学的理论研究和实际应用中经常遇到下类问题:在选定的一类函数中寻找某个函数g,使它是已知函数ƒ在一定意义下的近似表示,并求出用g近似表示 ƒ而产生的误差。这就是函数逼近问题。在函数逼近问题中,用来逼近已知函数ƒ的函数类可以有不同的选择;即使函数类选定了,

浪潮信息打造业界首款50℃进液温度服务器 PUE逼近理论极限1.0!

在科技飞速发展的今天,浪潮信息以其前瞻性的技术创新思维,再次突破行业极限,推出业界首个支持50℃进液温度的浸没式液冷服务器NF5180G7。这一创新成果不仅展现了浪潮信息在液冷技术领域的深厚实力,更标志着服务器冷却技术的一次重大飞跃。 NF5180G7是一款超高密度服务器,在1U空间内达到了性能、密度、扩展性最大化设计,支持2颗最高64核心350W最新英特尔至强可扩展处理器,最大支持32个DDR

给定函数的Chebyshev逼近

//计算给定函数的Chebyshev逼近 #include <iostream> #include <math.h> #include <fstream> #include <iomanip> using namespace std; const double pi = 3.141592653589793; class chebyshev { private:  int div, i, j,

设计普遍逼近的深度神经网络:一阶优化方法

论文地址:https://ieeexplore.ieee.org/document/10477580 传统的基于优化的神经网络设计方法通常从一个具有显式表示的目标函数出发,采用特定的优化算法进行求解,再将优化迭代格式映射为神经网络架构,例如著名的 LISTA-NN 就是利用 LISTA 算法求解 LASSO 问题所得 [4],这种方法受限于目标函数的显式表达式,可设计得到的网络结构有限。一些研究