C语言进阶:求最大公约数和最小公倍数
用c语言求最大最小公倍数是比较简单的操作,下面就让我为大家讲讲具体的操作吧。
操作方法
(01)组简单的公式是f(x, y) = f(y, x%y), f(x, y) = f(y, x - y) (x >=y > 0)。对于x和y,如果y = k * y1, x= k * x1,那么f(x, y) = k * f(x1, y1)。另外,如果x = p * x1,假设p为素数,并且y % p != 0,那么f(x, y) = f(p * x1, y) = f(x1, y)。取p = 2。
(02)函数功能: 求最大公约数 函数参数: x,y为两个数 返回值: 最大公约数 int gcd_solution1(int x, int y) if(y == 0) return x; else if(x < y) return gcd_solution1(y, x); else{ if(x&1) //x是奇数 if(y&1) //y是奇数 return gcd_solution1(y, x-y); else //y是偶数 return gcd_solution1(x, y>>1); else //x是偶数 if(y&1) //y是奇数 return gcd_solution1(x>>1, y); else //y是偶数 return gcd_solution1(x>>1, y>>1) << 1;
(03)求最小公倍数:最常用的是辗转相除法,有两整数a和b:① a%b得余数c② 若c=0,则b即为两数的最大公约数③ 若c≠0,则a=b,b=c,再回去执行①
(04)int gcd_solution2(int x, int y) { int result = 1; while(y) { int t = x; if(x&1) { if(y&1) { x = y; y = t % y; } elsey >>= 1; } else{ if(y&1) x >>= 1; else{ x >>= 1; y >>= 1; result <<= 1; } } } return result * x; }
-
ppt中怎样插入图表
ppt中经常用到图表,比如柱形图、圆饼图等,这些图就是基于一定的数据建立起来的,所以我们得先建立数据表格然后才能生成图表。下面提供了两种建立和插入图表的方法,原理其实是一样的。方法一:通过excel创建图表,然后复制到ppt中(01)打开excel,建立一个表格,基于这个表格中...
-
笔记本电脑win10如何快速取消“锁屏密码”?
日常工作生活中,除了工作和公众场所,私人以及家里电脑没有必要设置锁屏密码,每次登录输入一连串密码显得多余,已经设置的可以取消。下面介绍一下“笔记本电脑win10如何快速取消“锁屏密码”?”操作方法(01)右键点击桌面左下角“开始”——“运行”,打开“运行”对话框...
-
表格excel全空白没有线条边框网格线怎么办
Excel表格打开时,正常情况下都是有线条边框网格线的,但如果出现如图Excel表格全空白没有线条边框风格线的时候怎么办呢?接下来我就以Excel2010版本为例给大家提供几个解决方法。操作方法(01)方法一:打开Excel表格,单击选项,然后再把选项中的前的空格单击打上即可显示所...
-
如何管理win10的设备管理器检查硬件?
相信很多刚刚安装windows10正式版的用户一定发现了很多令人欣喜的功能改进,但是可能还不是很熟悉,尤其是对如何管理win10的设备管理器检查硬件,已达到完美的程度。下面就来详细讲解一下。操作方法(01)首先,你要做的是按下快捷键Win+X,然后在出现的快捷菜单中单击“控...