北大ACM1730Perfect Pth Powers总结

た入场券 2022-08-29 00:22 50阅读 0赞

思路：因为任何数总可以由某几个素因子(同一个素因子可以重复出现)相乘得到。  
设X = A^a \* B^b \* C^c,那么a, b, c三个数的最大公约数就是我们要求的结果。  
  
  
那们我们先求出0 - 68000所有素数。然后求出能被X整除的素数。分别他们的个数；  
再求最大公约数。

注意X可能是负数。如果是负数，我们检查最大公约数是否为偶数，如果是偶数我们就除2，直到变成奇数数了。

代码

\#include<stdio.h>  
\#include<math.h>  
\#include<string.h>  
  
  
int gcd( int a, int b );  
int T;  
  
  
int main()  
\{  
\_\_int64 x;  
int a\[68000\];  
int d\[6800\];  
int i;  
int t;  
int min;  
int repete;  
  
  
memset(a,0,sizeof(a));  
memset(d,0,sizeof(d));  
  
  
min = 0;  
for( i = 2; i < 68000; ++i )//算素数  
\{  
if( a\[i\] == 0 )//是素数  
\{  
a\[min++\] = i;//记下该素数，min记下素数的个数  
  
  
//该素数的倍数不可能为素数，所以以下代码标记哪些不为素数；  
repete = i + i;  
while( repete < 68000 )  
\{  
a\[repete\] = -1;//标记不为素数  
repete += i;  
\}  
/\*  
这里一开始写错了，搞了好久。  
错误代码：  
repete = i;  
while( repete < 68000 )  
\{  
repete += i;  
a\[repete\] = -1;这里repete的值可能已经 大于68000了，所以出错了  
\}  
\*/  
\}  
\}  
  
t = min;// 素数个数复制给t  
  
  
while( scanf( "%I64D", &x ) != EOF )  
\{  
T = 0;  
  
  
if( x == 0 )\{ break; \}  
  
  
if( x < 0 )\{ x = -x; T = 1;\}//输入为负数T标记为1  
  
  
min = sqrt( x + 0.0 );//x素因子的大小不可能比 根号X大。  
for( i = 0; i <= t; )  
\{  
  
  
if( a\[i\] > min || a\[i\] > x )break;  
if( x % a\[i\] == 0 )  
\{  
d\[i\]++;//记下该素因子的个数  
  
  
x /= a\[i\];  
if( x == 1 )  
\{  
break;  
\}  
\}  
else  
\{  
\++i;  
\}  
\}  
  
min = 0;  
for( i = 0; i <= t; ++i )//算最小公倍数  
\{  
if( d\[i\] != 0 )  
\{  
min = gcd( min, d\[i\] );  
d\[i\] = 0;  
\}  
\}  
  
  
if( min == 0 )  
\{  
min = 1;  
\}  
  
  
if( T == 1 )//处理负数情况  
\{  
while( min % 2 == 0 )  
\{  
min >>= 1;  
\}  
\}  
printf( "%d\\n", min );  
  
  
\}  
return 0;  
\}  
  
  
int gcd( int a, int b )  
\{  
if( b == 0 )  
\{  
return a;  
\}  
else  
\{  
return gcd( b, a % b );  
\}  
\}