ZSTU4270 同源数 2017-03-22 14:34 82人阅读 评论(0) 收藏
2024-09-25 05:34:02
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;
}
最新文章
- ruby 学习笔记 1
- 三维网格去噪算法(two-step framework)
- hadoop2.7.1安装
- 做HDU1010 带出来一个小问题
- Python读取Excel数据
- SSM三大框架整合详细教程
- 【蜗牛—漫漫IT路之大学篇(九) 
】
- storm serializable
- 【转】漫谈linux文件IO--io流程讲的很清楚
- 数据结构——Java实现链栈
- (1)wr703n刷openwrt智能控制--配置wifi
- Java Spring 在线程中或其他位置获取 ApplicationContext 或 ServiceBean
- Delphi XE7试用记录1
- Java 数据驱动测试
- 从angularjs传递参数至Web API
- Codeforces Round #467 (Div. 2) E	-Lock Puzzle
- Shell脚本编程(二):shell变量
- IOS初级:导航控制器
- 【Linux】开机自动启动脚本
- clapack在android上移植
热门文章
- centos 6.5 下 安装 git
- emacs配置buffer的快捷键
- HDU 4586 Play the Dice(数学期望)
- Hive新功能 Cube, Rollup介绍
- javascript中不存在块级作用域,所以要小心使用在块级作用域中的函数声明所带来的作用域混乱.
- windows拖动文件到Ubuntu
- django-redis缓存
- 3_bootsrap布局容器
- Rhythmk 一步一步学 JAVA (22) JAVA 网络编程
- Windows下python3安装pip管理包(转贴)