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; }


推荐相关:

最大公约数与最小公倍数练习题之一

填空题。 1. 都是自然数,如果 , 的最大公约 数是( ),最小公倍数是( )。 2. 甲 ,乙 ,甲乙的最大公约数是 ()×()=(),甲和 ...


最大公约数与最小公倍数练习题

最大公约数和最小公倍数练习题 一. 填空题。 1. 所有自然数的公约数为( )。 2. 如果 m 和 n 是互质数,那么它们的最大公约数是( ),最小公倍数是( ...


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

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


最大公约数与最小公倍数习题

最大公约数与最小公倍数习题_四年级数学_数学_小学教育_教育专区。竞赛习题选配最大公约数与最小公倍数 1. n 个不同的正整数中, a , A 分别是其中最小数...


最大公约数和最小公倍数练习题[无]

最大公约数和最小公倍数练习题[无]_小学作文_小学教育_教育专区。最大公约数和最小公倍数练习题 一. 填空题。 1. 都是自然数,如果,的最大公约数是() ,...


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

最小公倍数和最大公约数练习题_五年级数学_数学_小学教育_教育专区。最大公约数和最小公倍数练习题一、直接说出每组数的最大公约数和最小公倍数。 26 和 13...


最大公约数与最小公倍数练习题

最大公约数与最小公倍数练习题_数学_小学教育_教育专区。关于最大公约数与最小公倍数的一些习题今日推荐 50份文档 2014年注册会计师考试 ...


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

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


最小公倍数和最大公约数练习题答案一份

最小公倍数和最大公约数练习题答案一份_数学_小学教育_教育专区。1.两个数的最大公因数是 6,最小公倍数是 144,这两个数的和是( 11.25 2.2520,14850,...


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

最大公约数和最小公倍数练习题_从业资格考试_资格考试/认证_教育专区。一.填空题。 1.都是自然数,如果,的最大公约数是() ,最小公倍数是()。 2.甲,乙,...

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