Mysterious Bacteria LightOJ

Mysterious Bacteria LightOJ - 1220

阅读量：4550 次

发布时间：2019-06-08

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

题意：

给出一个数x 求 x = b^p 的p的最大值

解析：

算术基本定理分解质因数

任何一个数x都可以表示为 x == p₁^a1 * p₂^a2 * ````` * p_n^an

即 b^p== p₁^a1 * p₂^a2 * ````` * p_n^an== (p₁^b1* p₂^b2 * `````` * p_n^bn)^p

所以 p_max == gcd（a1，a2，·····，an）；

如果x是一个负数则p只能为奇数

先把x换成正数求出最大p之后如果x 为负则不断除2 直至p为奇数

代码如下：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #define MOD 2018#define LL long long#define ULL unsigned long long#define maxn 1000100#define Pair pair
                
                 #define mem(a, b) memset(a, b, sizeof(a))#define _ ios_base::sync_with_stdio(0),cin.tie(0)//freopen("1.txt", "r", stdin);using namespace std;const int LL_INF = 0x7fffffffffffffff,INF = 0x3f3f3f3f;int primes[maxn];bool vis[maxn];int ans = 0;LL gcd(LL a, LL b){ return b==0?a:gcd(b,a%b);}void init(){ mem(vis,0); for(int i=2; i
                 
                   0) { if(res == 0) res = cnt2; res = gcd(res, cnt2); } } if(n > 1) { res = 1; } if(flag) { while(res % 2 == 0) res /= 2; } printf("Case %d: %d\n",++kase,res); } return 0;}