tceic.com
学霸学习网 这下你爽了
相关标签
当前位置:首页 >> 学科竞赛 >>

noip最大公约数与最小公倍数问题题解


在看程序之前,请看一下我的证明过程,不然你不懂我的程序的。 在 P、Q 存在时(第四组数据就是 P、Q 不存在的情况) p=n*x;q=m*x;n、m 互质; y*x=p*q(y=n*m*x); 所以我只用找出 y/x 的质因数个数,再组合一下就可以了。(样例 3 60 的 y/x=20=2*2*5, 质因数为 2、5) 由二项式定理得:有 n 个质因数就有 2^n 种组合方式。

#include<iostream> #include<cmath> using namespace std; bool ok; int x,y,b,i,j,s[1000],na; int main() { cin>>x>>y; if(y%x!=0){cout<<'0';return 0;}//验证不存在的情况 na=s[0]=1; s[1]=2; b=y/x; if(b%2==0)na=2;//我后面的程序无法验证 2 是否为质因数,所以加了个判断 for(i=3;i<=b;i++) { ok=1; for(j=1;j<=s[0];j++)if(i%s[j]==0){ok=0;break;}//找质数,相当于打表 if(ok) {s[0]++;s[s[0]]=i;if(b%i==0)na=na*2;} //质数入队,方便判断质数。判断是否为质因数,是则加倍 } cout<<na; return 0; }


推荐相关:

NOIp06-15题解分析

但结论很容易猜出)+求逆序对个数 3.货车运输:最大生成树+树上求路径最小值...解,第二次记录能到达最后一行的点,转换为经典 得线段覆盖问题 noip2009 题 1...


奥数最大公约数与最小公倍数例题、练习及答案

2.通过比较与辨析,使学生进一步理解和掌握“最大公约数和最小公倍数应用题的解 最大公约数与最小公倍数(一)教学目标: 1.通过学生对应用题的条件与问题的...


求最大公约数和最小公倍数练习题

最大公约数和最小公倍数练习题_五年级数学_数学_小学教育_教育专区。小学5年级数学 求最大公约数和最小公倍数练习题 1、 有短除法求下面各数的最大公约...


NOIP2014 题解

NOIP2014 题解_IT/计算机_专业资料。NOIP2014 题解 D1T1 : 生活大爆炸版石头剪刀布(rps) 100% : 模拟。另一种方法,可以先求出 na,nb 的最小公倍数 l,...


最大公约数和最小公倍数练习题 姓名

最大公约数和最小公倍数练习题 姓名_学科竞赛_小学教育_教育专区。最大公约数和最小公倍数练习题 一. 填空题。 1.a 和 b 都是自然数,如果 和 b 最小...


公约数与公倍数拔高题答案

公约数与公倍数拔高题答案_学科竞赛_小学教育_教育专区。董老师 VIP 公约数与公倍数拔高题答案 1:有两个两位数,这两个两位数的最大公约数与最小公倍数的...


小学五年级数学最大公约数和 最小公倍数应用题

小学五年级数学最大公约数和 最小公倍数应用题_五年级数学_数学_小学教育_教育专区。小学五年级数学讲义 最大公约数和最小公倍数应用题 应用最大公约数与最小...


noip2015普及组题解最终

noip2015普及组题解最终_学科竞赛_小学教育_教育专区...【问题描述】 扫雷游戏是一款十分经典的单机小游戏。...超过距离范围的(疲劳值+增加的往返距离值)最大 值...


第五讲 最大公约数与最小公倍数

第五讲 最大公约数与最小公倍数_五年级数学_数学...解:由 ab=[a,b]×(a,b)可得:另一个数为,...解:由题意可得:560÷20=28=1×28=4×7,显然 ...


五年级奥数最大公约数问题

专题推荐 五年级奥数数阵问题 五年级奥数最小公倍数1/2 相关文档推荐...但是这题中,长 宽的数比较大,最大公约数比较难求出,这里再介绍一种求两...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com