数论(GCD) HDOJ 4320 Arcane Numbers 1-白红宇

数论(GCD) HDOJ 4320 Arcane Numbers 1

阅读量：5916 次

发布时间：2019-06-19

本文共 1170 字，大约阅读时间需要 3 分钟。

题意：有一个A进制的有限小数，问能否转换成B进制的有限小数

分析：0.123在A进制下表示成：1/A + 2/(A^2) + 3 / (A^3)，转换成B进制就是不断的乘B直到为0，即(1/A + 2/(A^2) + 3 / (A^3)) * (B^m)。那么(B^m) 一定要能整除(A^n)，转换一下就是A的质因子B都有，可以用GCD高效计算

收获：数论题做不来可以找找规律，想想会用什么知识求解

代码：

/************************************************* Author        :Running_Time!* Created Time  :2015-8-25 8:49:59* File Name     :A.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int MAXN = 1e5 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;ll GCD(ll a, ll b) { return b == 0 ? a : GCD (b, a % b);}int main(){ int T, cas = 0; scanf ("%d", &T); ll A, B, C; while (T--) { scanf ("%I64d%I64d", &A, &B); while ((C = GCD (A, B)) != 1) A /= C; printf ("Case #%d: %s\n", ++cas, A == 1 ? "YES" : "NO"); } return 0;}

转载于:https://www.cnblogs.com/Running-Time/p/4758672.html

你可能感兴趣的文章