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


赞助商链接
推荐相关:

...数的计算【NOIP2001普及组】 1111 公约数与公倍数【...

公约数与公倍数【NOIP2001 普及组】 Time Limit:10000MS Memory Limit:65536K Total Submit:6 Accepted:4 Description 最大公约数和最小公倍数问题 输入二个正...


NOIP2015提高组题解zkp蒟蒻的题解

NOIP2015 提高组题解——By zkp 蒟蒻 第一天: 第一题 幻方 纯模拟 第二题 信息传递 对于每一个未访问过的节点,访问其父节点,直到当前结点 曾被访问过,之后...


历年NOIP(普及组提高组)试题分析

历年NOIP(普及组提高组)试题分析_IT认证_资格考试/认证_教育专区。历年 NOIP(普及...最大公约数和最小公倍数 求先序排列 装箱问题 级数求和 选数 产生数 过河...


NOIP2015提高组解题报告

NOIP2015 提高组解题报告 T1 神奇的幻方【题目大意...地主手牌,问你最快几次出完,数据随机,牌数不超过...⑤ 95 分做法:把航线从大到小排序,我们要求的就...


NOIP2014提高组第二试题解

NOIP2014提高组第二试题解_IT认证_资格考试/认证_教育专区。NOIP2014提高组第二...最后寻找最大值并进行计数即可, 写代码还是结构化一点比较舒服, 标程如下: 1...


noip 2011 c++题解

noip 2011 c++题解_解决方案_计划/解决方案_应用文书。2011niopc++题解(NOIP2011)普及组复赛 1.数字反转 (reverse.cpp/c/pas) 【问题描述】 给定一个整数,请...


noip完整考纲

(二) 数论 求最大公约数最大公约数最小公倍数最小公倍数 ★...NOIP初赛培训 70页 免费 NOIP题目方向 6页 免费 NOIP复习 81页 免费 NOIP初赛...


NOIp2009题解 + A星算法

最小费用, 而此路径的最大获利便是取获利最大...NOIP2009 靶形数独解题报告 这题困扰了我差不多有...如果该数独无解,输出-1。 【题目分析】 数独问题...


NOIP2009提高组复赛题解

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


NOIP2009提高组复赛题解

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

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