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


推荐相关:

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

noip最大公约数与最小公倍数问题题解_学科竞赛_高中教育_教育专区。在看程序之前,请看一下我的证明过程,不然你不懂我的程序的。 在 P、Q 存在时(第四组数...


NOIP2009提高组复赛题解

NOIP2009提高组复赛题解_高考_高中教育_教育专区。noip历届复赛试题及解析1...那么我们可以去枚举 a1 的倍数,然 后去验证最大公约数和最小公倍数是否符合...


NOIP2009提高组复赛题解

NOIP2009 提高组复赛题解(1) 2010-02-21 19:38 1. 潜伏者 (spy.pas/c/...1、 x 和 a0 的最大公约数是 a1; 2、 x 和 b0 的最小公倍数是 b1。...


数论

2002 题二 最大公约数与最小公倍数问题 (20分) [问题描述] 输入二个正...【输入样例】 3 100 【输出样例】 981 2005 年 noip 普及组 循环 (circle....


Noip2001年普及组复赛题目

Noip2001年普及组复赛题目_IT/计算机_专业资料。Noip2001年普及组复赛题目NOI...最大公约数和最小公倍数问题(20 分) 题二 最大公约数和最小公倍数问题 ...


NOIP复赛谈

方格取数 数的计数 最大公约数与最小公倍数 二叉树的先序序列 装箱问题 一...类似的题目,一些比赛中也出现过这一问题的变形(如 NOIP1997 初中组的第三题)...


NOIP复赛谈

方格取数 数的计数 最大公约数与最小公倍数 二叉树的先序序列 装箱问题 一...类似的题目,一些比赛中也出现过这一问题的变形(如 NOIP1997 初中组的第三题)...


2000-2011NOIP普及组

年份2000 2000 2000 2000 题名 计算器的改良 税收与补贴问题 乘积最大 单词...136 【01NOIP 普及组】最大公约数与最小公倍数(gygb.pas) 【题目描述】 ...


NOIP复赛谈

NOIP初赛谈1 29页 免费 noip复赛 2页 免费 NOIP复赛题集 11页 5财富值 第...方格取数 数的计数 最大公约数与最小公倍数 二叉树的先序序列 装箱问题 一...


初级算法习题集

一些初级的NOIP的提 算法设计题集 第 1 页共 30...1.待解问题的描述 待解问题表述应精确、简练、清楚...{求最小公倍数} {求最大公约数} l:=lcm(m,...

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