从某个地方找到的解题报告：
题目大意是求n=x^p的最大p值，n、x、p均为整数。
p的最大值即为x的所有素数因子的个数的最大公约数。如果n为负数且p可整除2则需一直整除直到无法整除为止。
下面是我的代码，方法差不多了，不知道为什么还AC不了，大虾给点测试数据或者指点一下吧
#include <stdio.h>
#include <math.h>
#define PSIZE 6542 

int primes[PSIZE];
int m[64];
int pos[64];
int st;

int gcd(int a,int b)   
{   
	if (b==0)  return a;   
	else return gcd(b, a % b);   
} 

int mgcd(int* arr, int size)
{
	int ret = arr[0];
	int i;
	for(i = 0; i < size; i++)
	{
		ret = gcd(ret, arr[i]);
	}
	return ret;
}

void CreatePrime()
{
	int cnt;
	int to = 65536;
	bool good;
	int m;
	int i, j;
	cnt = 0;
	for(i = 2; i <= to; i++)
	{
		m = (int)sqrt(i);
		good = true;
		for(j = 0; j < cnt && primes[j] <= m; j++)
		{
			if(i % primes[j] == 0)
			{
				good = false;
			}
		}
		if(good)
		{
			primes[cnt++] = i;
		}
	}	
}

int main()
{
	int x;
	bool p;
	int i;
	int count;
	int sqx;
	int r;
	CreatePrime();
	while(scanf("%d", &x) != EOF && x != 0)
	{
		p = (x > 0);
		x = (x > 0) ? x : -x;		
		st = 0;
		sqx = (int)sqrt(x);
		
		for(i = 0; i < PSIZE && primes[i] <= sqx; i++)
		{
			count = 0;
			while(x % primes[i] == 0)
			{
				x = x / primes[i];
				count ++;
			}
			if(count > 0)
			{
				m[st] = primes[i];
				pos[st] = count;
				st++;
			}			
		}

		if(x != 1)
		{
			m[st] = x;
			pos[st] = 1;
			st++;
		}
		
		r = mgcd(pos, st);
		if(!p)
		{
			while(r % 2 == 0) r /= 2;			
		} 
		
		printf("%d\n", r);
				
	}
	return 0;
}

• Re:纯数学解决的方法 (34) sanmu 2010-08-06 10:58:47
• Re:纯数学解决的方法 (19) windows8 2010-08-24 22:02:29
  • Re:纯数学解决的方法 (11) windows8 2010-08-24 22:27:57