`
lovnet
  • 浏览: 6672190 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
文章分类
社区版块
存档分类
最新评论

HDU 4320 Arcane Numbers 1(12年多校3-数学)

 
阅读更多

题目链接: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;
}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics