题目链接:Click here~~
题意:
给你任意一个 p 进制下有限位数的数 n,问是否一定能转化成 q 进制下有限位数的数字 m。
解题思路:
显然若 n 为整数,一定可以,那么我们下面分析一下 n 含小数的情况。
设 n 的小数部分为 x,且小数部分共 k 位,第 i 位上的数字为 ai。
那么我们可以将 x 表示成下面式子的形式:
。
而在进制转化中,整数部分是“除基倒取余”,小数部分是“乘基正取整”,且乘到小数部分为0时截止。
于是问题转化成了 x 在什么时候小数部分“乘基”一定会变成0。
由 x 的表达式我们可知,当且仅当乘数中含有 p^k 这个因子时,x 的小数部分才为0。
那么就相当于判断 q^h 中是否含有 p^k 这个因子(h 可无限大)。
又由算术基本定理,p^k 中的质因子一定和 p 中的相同。
所以只要 q 中包含 p 的所有质因子,就必定存在 h 使得 q^h 中包含 p^k 这个因子,从而使问题有解。
那么,如何判断 q 中是否包含 p 的所有质因子呢?
1、若 p 和 q 不互质,则只需要判断 q 中是否包含 p/gcd(p,q) 的所有质因子。
2、若 p 和 q 互质,当且仅当 p = 1 时,q 中包含 p 的所有质因子。
#include <stdio.h>
__int64 gcd(__int64 a,__int64 b)
{
return b ? gcd(b,a%b) : a;
}
int main()
{
int z,ncase = 0;
__int64 a,b,t;
scanf("%d",&z);
while(z--)
{
scanf("%I64d%I64d",&a,&b);
while((t=gcd(a,b)) != 1)
a /= t;
printf("Case #%d: ",++ncase);
puts(a-1?"NO":"YES");
}
return 0;
}
分享到:
相关推荐
2017hdu多校联合训练第一场标程及数据
2019 Multi-University Training Contest 4(2019hdu多校第六场数据与标程)
2019 Multi-University Training Contest 4(2019hdu多校第五场数据与标程),欢迎大家下载
HDU2013暑期多校联合训练第一场0723-解题报告和标程
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
2-sat---hdu3062,代码详尽,清晰,格式规范,亲测无误。
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
ACM/ICPC 2010年多校联合第十场第九题的解题报告及代码,AC代码有三个,最好的是src
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
这份压缩爆内包含了2019年杭电多校第二场的数据与标程,欢迎下载
HDU 1010-2500解题报告,ACMer可以借鉴一下
hdu2000-2014ac代码,虽然只有几道,但都是简单的
HDU的ACM,非常的好 涉及了很多算法,例如二分匹配、博弈、组合、最小生成树、搜索、动态规划、贪心算法
有2019 Multi-University Training Contest 4,hdu多校第四场的题解,数据标程,有需要的可以下载哦
华为HLR相关资料,介绍了HLR中的HDU数据库单元原理
ACM入门的课件适合于那些想要学习的ACM,提高自己编程能力的。
有2019 Multi-University Training Contest 9,hdu多校第9场的题解,数据标程,有需要的可以下载哦
示例 1:示例 2:解答:大小写转换: n = n ^ 32转小写: n = n | 32转大写: n = n & -33const toLowerCase =
2014 Multi-University Training Contest 1多校联合赛标程和部分数据。