幾道簡單ACM題的解答----1

從這篇開始，發一些簡單的ACM題及其解答，都是這幾天做的。

題目：

破解平方數Problem

給出m個數b1, b2,..., bm,每個數的素數因子都在前t個素數之内，任務是尋找這m個數的非空子集的個數x，使得每個子集的乘積都是一個完全平方數。例如t=3,則前3個素數為2, 3, 5。m=4，這4個數為9, 20, 500, 3， 每個數的素因子都是在前3個素數内，則有x=3個非空子集合{9}， {20， 500}， {9， 20， 500}，滿足每個集合内的數的乘積是一個完全平方數，輸出這樣的集合的個數。 

Input

每組測試資料的第一行為兩個正整數t, m(1 ≤ t ≤ 100, 1 ≤ m ≤ 100) 第二行為m個數， 1 <= bi <= 109 處理至檔案結束 

Output

每行輸出一個整數x，對應每組測試資料 

Sample Input

3 4

9 20 500 3

Sample Output

3

我的答案：

#include<stdio.h>
#include<math.h>

#define MAX 100
#define SUCCESS 1
#define FAILURE 0

void makePrime(int prime[],int t);
void makeMatrix(char matrix[],int m,int i);
int test(int data[],int prime[],char matrix[],int m,int t);
int isPrime(int prime[],int length,int testNum);
void addArray(int array[],int num,int prime[],int t);

int main()
{
	int t,m;
	int prime[100];
	char matrix[100];
	int data[100];
	int sum = 0;
	int i;
	
	prime[0] = 2;
	
	scanf("%d%d",&t,&m);
	for(i = 0;i < m;i++)
		scanf("%d",&data[i]);
	/*for(i = 0;i < m;i++)
		printf("%d\t",data[i]);*/	
	makePrime(prime,t);
	for(i = 1;i < (int)pow(2,m);i++)
	{
		makeMatrix(matrix,m,i);
		if(test(data,prime,matrix,m,t) == SUCCESS)
			sum++;
	}	
	printf("%d\n",sum);
	return 0;
}

void makePrime(int prime[],int t)
{
	int i = 1;
	int j;
	//int k;
	
	
	for(j = 3;i < t;j += 2)
		if(isPrime(prime,i,j))
		{
			++i;
			prime[i - 1] = j;
		}
	
	/*for(k = 0;k < t;k++)
	{
		printf("%d\t",prime[k]);
	}*/
}

void makeMatrix(char matrix[],int m,int i)
{	
	//化成二進制的函數
	m--;
	for(;m >= 0;m--)
	{
		matrix[m] = i % 2 + '0';
		i /= 2;
		//putchar(matrix[m]);
	}
	//putchar('\n');
}

int test(int data[],int prime[],char matrix[],int m,int t)
{
	int i;
	int array[MAX] = {0};
	
	/*printf("testing ");
	for(i = 0;i < m;i++)
		putchar(matrix[i]);	
	putchar('\n');*/
	//printf("m == %d\n",m);
	for(i = 0;i < m;i++)
		if(matrix[i] == '1')
			addArray(array,data[i],prime,t);
		
		
	/*for(i = 0;i < m;i++)
		printf("%3d",array[i]);
	*/
	for(i = 0;i < m;i++)
	{
		if(array[i] % 2 != 0)
			return FAILURE;	
	}
	return SUCCESS;
	//為什麼對于多個1就沒用了？
}

int isPrime(int prime[],int length,int testNum)
{
	int i;
	
	for(i = 0;i < length;i++)
	{
		if(testNum % prime[i] == 0)
			return 0;
	}
	return 1;
}

void addArray(int array[],int num,int prime[],int t)
{
	int i;
	for(i = 0;i < t;i++)
	{
		while(num % prime[i] == 0)
		{
			array[i]++;
			//printf("%d++\n",i);
			if(num >= prime[i])	
				num = num / prime[i];
			//else
			//	break;
		}		
	}
}
           

PS：我感覺這個題目的資料是有問題的，如果真的測試資料t和m到了100的話，那麼程式會測試2的100次方個資料，這是個相當大的資料。