【题目】
题目详情
小强最近在学初等数论,老师给他们出了一个课后习题,那就是给你两个正整数A,B(0<A,B<2^60),判断他们的素因子集合是否相同,小强刚接触数论,想了好一会还是没能想出来,你能帮助他吗?
输入描述:
输入包含多组测试数据,每组测试数据包含两个正整数A,B,以文件结束。
输出描述:
对于每组测试数据如果A和B的素因子集合相同则输出“YES”,否则输出“NO”。
答题说明
输入样例:
2 8
4 9
10 50
输出样例:
YES
NO
YES
【分析】
唯一质因子分解定理:任意一个合数a仅能以一种方式,写成如下的乘积形式:
a = p1^e1*p2^e2*...*pr^er
其中pi为素数,p1<p2<...<pr,且ei为正整数。例如数6000=2^4*3*5^3。
【代码】
/*********************************
* 日期:2014-04-29
* 作者:SJF0115
* 题目: 素因子集合
* 来源:http://hero.csdn.net/Question/Details?ID=506&ExamID=501&from=211
* 结果:AC
* 来源:庞果网
* 总结:
**********************************/
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define N 1000000
long long set[N],set2[N];
//素因子集合
int PrimeSet(long long n,long long *set){
int num = 0;
for(long long i = 2;i*i <= n;i++){
if(n % i == 0){
set[num++] = i;
while(n % i ==0){
n = n / i;
}
}//if
}//for
if(n > 1){
set[num++] = n;
}
//返回素数集合的个数
return num;
}
int main(){
int i;
long long a,b;
while(scanf("%lld%lld",&a,&b) != EOF){
memset(set,0,sizeof(set));
memset(set2,0,sizeof(set2));
int num = PrimeSet(a,set);
int num2 = PrimeSet(b,set2);
if(num != num2){
printf("NO\n");
}
else{
for(i = 0;i < num;i++){
if(set[i] != set2[i]){
printf("NO\n");
break;
}
}//for
if(i >= num){
printf("YES\n");
}//if
}//if
}//while
return 0;
}
分享到:
相关推荐
C语言,用递归算法实现素因子分解,方法简洁明了
素因子分解c语言
uva11859nim游戏 + 求素因子个数.cpp
蓝桥杯练习系统的试题:算法训练 素因子去重个人所做的答案。 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
给定某个正整数N,求其素因子分解结果,即给出其因式分解表达式 N = p1^k1 * p2^k2 *…*pm ^km。 输入格式说明: 输入long int范围内的正整数N。 输出格式说明: 按给定格式输出N的素因式分解表达式,即 N = p1^...
番茄果实中抗冷转录因子 LeCBF1 基因片段的克隆与表达分析,赵丹莹,生吉萍,本研究通过在低温胁迫处理后的番茄果实中克隆抗冷关键转录因子 LeCBF1 基因片段,首次证明了该基因在植物果实中可受冷诱导表达。...
素因子不超过17的有限单群的新刻画,张盟盟,张良才,若存在k个互补同构的群与群G具有相同的群阶和素图度数序列,则称群G是可k重OD-刻画的,特别地,若k=1,则称群G是可OD-刻画的。本文主要
关于Fibonacci 数中含有形如4p+1的素因子,马玉林,,本文将用初等数学的方法证明下标素数 p为何值的情况下,Fibonacci数 F_p具有形如 4p+1的素因子。本文给出如下的结论:如果素数p>7 ,p=2(mo
素因子分解c语言
20161220-华泰证券-多因子系列之四:单因子测试之动量类因子.pdf
20160929-华泰证券-多因子系列之二:华泰单因子测试之估值类因子(2).pdf
试题 算法训练 素因子去重 资源限制 时间限制:1.0s 内存限制:256.0MB 问题描述 给定一个正整数n,求一个正整数p,满足p仅包含n的所有素因子,且每个素因子的次数不大于1 输入格式 一个整数,表示n 输出格式 ...
龙眼生长素响应因子ARF3密码子偏好性分析,赖瑞联,林玉玲,为了解生长素响应因子密码子使用特性,试验采用CodonW、SPSS软件及EMBOSS在线程序等分析龙眼ARF3密码子偏好性,并分别与龙眼ARF其它成员�
论文研究-FF因子与宏观因子是潜在风险... (2) 基于工业总产值增长率、通货膨胀率、银行同业拆借利率以及M2 增长率构造宏观经济因子,发现单个宏观经济因子和整个宏观经济因子集合都不适合作为投资组合风险因子的代理.
量价因子专题报告:量价因子之单因子测试.pdf
20170410-光大证券-光大证券多因子系列报告之一:因子测试框架.pdf
脉冲因子、波形因子、裕度因子、峰值因子、偏度、峭度.m
2. 多因子模型建立流程 11 3. 单因子测试结果 13 4. 结论 35
姜黄素调节转录因子抗肿瘤机制,戴海燕,陈震,姜黄素是从姜黄属的姜黄中提取的一种多酚类物,研究表明姜黄素具有抗菌抗病毒、促进伤口愈合,抗炎,免疫调节等药理作用,特别是