4270: 同源数

Time Limit: 3 Sec  Memory Limit: 128 MB

Submit: 1284  Solved: 224

Description

如果x和y的质因子集合完全相同,那么我们就说他们是同源的。
比如说18 = 2 * 32,12 = 3 * 22;

Input

本题有多组数据(组数 <= 555555)。
每组数据输入形如:
x y
x, y为整数(1 <= x, y <= 1e18)

Output

输出形入:
ans
如果x, y为同源数,那么ans为”Yes”, 不然为”No”.

Sample Input

18 12
2 3

Sample Output

Yes
No

——————————————————————————————

判断两个数是否质因子相同。我们不难想到如果两个数的质因子和他们的最大公约数相同,那么他们肯定是同源数,所以求出GCD不断算公约数即可
#include<map>
#include<set>
#include<ctime>
#include<cmath>
#include<queue>
#include<bitset>
#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define inf 0x3f3f3f3f long long gcd(long long a,long long b)
{
return b==0?a:gcd(b,a%b);
} int main()
{ long long x,y;
while(~scanf("%lld%lld",&x,&y))
{
long long t=gcd(x,y);
x/=t;
y/=t;
long long a;
while(x!=1)
{
a=gcd(t,x);
if(a==1) break;
x/=a;
} while(y!=1)
{
a=gcd(t,y);
if(a==1) break;
y/=a;
}
if(x!=1||y!=1)
printf("No\n");
else
printf("Yes\n");
} return 0;
}


最新文章

  1. ruby 学习笔记 1
  2. 三维网格去噪算法(two-step framework)
  3. hadoop2.7.1安装
  4. 做HDU1010 带出来一个小问题
  5. Python读取Excel数据
  6. SSM三大框架整合详细教程
  7. 【蜗牛—漫漫IT路之大学篇(九) 】
  8. storm serializable
  9. 【转】漫谈linux文件IO--io流程讲的很清楚
  10. 数据结构——Java实现链栈
  11. (1)wr703n刷openwrt智能控制--配置wifi
  12. Java Spring 在线程中或其他位置获取 ApplicationContext 或 ServiceBean
  13. Delphi XE7试用记录1
  14. Java 数据驱动测试
  15. 从angularjs传递参数至Web API
  16. Codeforces Round #467 (Div. 2) E -Lock Puzzle
  17. Shell脚本编程(二):shell变量
  18. IOS初级:导航控制器
  19. 【Linux】开机自动启动脚本
  20. clapack在android上移植

热门文章

  1. centos 6.5 下 安装 git
  2. emacs配置buffer的快捷键
  3. HDU 4586 Play the Dice(数学期望)
  4. Hive新功能 Cube, Rollup介绍
  5. javascript中不存在块级作用域,所以要小心使用在块级作用域中的函数声明所带来的作用域混乱.
  6. windows拖动文件到Ubuntu
  7. django-redis缓存
  8. 3_bootsrap布局容器
  9. Rhythmk 一步一步学 JAVA (22) JAVA 网络编程
  10. Windows下python3安装pip管理包(转贴)