（Problem 29）Distinct powers

Consider all integer combinations of a^b for 2  a  5 and 2  b  5:

2²=4, 2³=8, 2⁴=16, 2⁵=32
3²=9, 3³=27, 3⁴=81, 3⁵=243
4²=16, 4³=64, 4⁴=256, 4⁵=1024
5²=25, 5³=125, 5⁴=625, 5⁵=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by a^b for 2  a  100 and 2  b  100?

 

题目大意：

考虑 a^b 在 2  a  5，2  b  5下的所有整数组合：

2²=4, 2³=8, 2⁴=16, 2⁵=32
3²=9, 3³=27, 3⁴=81, 3⁵=243
4²=16, 4³=64, 4⁴=256, 4⁵=1024
5²=25, 5³=125, 5⁴=625, 5⁵=3125

如果将这些数字排序，并去除重复的，我们得到如下15个数字的序列：

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

a^b 在 2  a  100，2  b  100 下生成的序列中有多少个不同的项？

 

算法设计（方法1）：

 1、将a^b 进行因数分解，以字符串的形式保存，eg.  28⁵ = (4 * 7)⁵ = (2² * 7)⁵  = 2^10*7^5

 2、用一个结构体数组保存所有的数的因数分解表达式

 3、对上述结构体数组排序

 4、遍历此数组，找出不相同的项的总数

#include <stdio.h> 
#include <string.h>

const int prim[25] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,41,
					  43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};

struct node
{
   char list[100];

}num[9801];

int cmp(const void *a, const void *b)
{
	return strcmp((*(struct node*)a).list, (*(struct node*)b).list);
}

char * explain(int a, int b)   /*将a^b分解因数*/
{
	char s[100], ch;
	char *p;
	p = s;
	int t;
    for(int i = 0; i < 25; i++) {
		t = 0;
        while(a % prim[i] == 0) {
			if(t == 0) {
				sprintf(p,"%d",prim[i]);
			}
            a /= prim[i];
			t++;
        }
		if(t > 0) {
			p = s + strlen(s);
			*p++ = '^';
			t = t * b;
			sprintf(p,"%d",t);
			p = s + strlen(s);
			if(a != 1) {
				*p++ = '*';
			} else {
				break;
			}
		}
    }
	return s;
}

void solve(void)
{
	int i, j, k, sum;
	k = 0;
	for(i = 2; i < 101; i++) {
		for(j = 2; j < 101; j++) {
			strcpy(num[k++].list, explain(i,j));
		}
	}
	qsort(num, 9801, sizeof(num[0]),cmp);
	sum = 1;
	for(i = 0; i < 9801; ) {
		j = i + 1;
		if(j >= 9801)  break;
		while(strcmp(num[i].list, num[j].list) == 0) {
			j++;
		}
		i = j;
		sum ++;
	}
	printf("%d\n",sum);
}

int main(void)
{
	solve();
    return 0;
}

 

算法设计（方法2）：

 仔细考察数字矩阵的规律，可以发现：

    能够发生重复的数字，将他们因数分解以后，得到的指数的底都是相同的，e.g. 16与64……，在2~100中，能够发生重复数字的底只有4、8、16、32、64、9、27、81、25、36、49、81、100，于是可以在底为2的时候就排除掉以4、8、16、32、64为底的重复的数字。

#include<stdio.h>   
#include<stdbool.h>
#include<stdlib.h>

#define N 101
#define M 601

int main(void)
{
 int answer = 0;
 int i, j, k, l;
 bool flag[M];

 bool use[N] = {false};  

 for (i = 2; i < N; i++)
 {
  if (!use[i])
  {
   int t = i;

   memset(flag, false, sizeof(flag));

   for (j = 2; j < N; j++)
   {
    t = t * i;
    if (t >= N)
    {
     break;
    }
    use[t] = true;
   }

   for (k = 1; k < j; k++)
   {
    for (l = 2; l < N; l++)
    {
     flag[k*l] = true;
    }
   }

   for (k = 2; k < M; k++)
   {
    if(flag[k]){
     answer++;
    } 
 
   }
  }
}
 printf("%d\n",answer);
 return 0;
}

 

Answer:

9183

 

Completed on Tue, 19 Nov 2013, 07:28