Project Euler——Problem 29 - Daybreakcx's Blog - Keep Programming! With Algorithm! With Fun!
Project Euler——Problem 28
Project Euler——Problem 30

Project Euler——Problem 29

daybreakcx posted @ 2009年7月27日 18:58 in Prject Euler , 1215 阅读

原题与答案:

Problem 29

25 October 2002

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

2^(2)=4, 2^(3)=8, 2^(4)=16, 2^(5)=32
3^(2)=9, 3^(3)=27, 3^(4)=81, 3^(5)=243
4^(2)=16, 4^(3)=64, 4^(4)=256, 4^(5)=1024
5^(2)=25, 5^(3)=125, 5^(4)=625, 5^(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?

Answer:9183

 

分析与解答:

题目的意思是由在[2,100]区间中的a和b由a^b形式构成的数有多少个。首先我们先确定一点,那就是a_1^{b_1}=a_2^{b_2}这样的情况是存在的,比如2^4=4^2,那么也就是说有重复的数值存在,其次是我们是否需要求出每一个数值的具体大小呢?答案是否定的,在[2,100]区间中,我们得到的最大数值是100^{100},大概有201位,直接去算那么数值比较大,而且比较也很久,我们就要想换一种方法。我们利用一个更快的方法来进行,假设a的质因素分解形式是a=p_1^{s_1}*p_2^{s_2}*...*p_k^{s_k},那么a^b=p_1^{b*s_1}*p_2^{b*s_2}*...*p_k^{b*s_k},我们可以将所有的数值都化成质因素分解的形式,这样我们只需要比较对应的次数,而且在100内的素数只有25个,比较的个数比较少。每次我们分解出a的形式,然后对于a^b只要将次数都乘以b,就可以了,最后将这些次数序列排个序,计算有多少种即可,我的源程序代码如下所示:

 

  1. #include<stdio.h>
  2. #include<memory.h>
  3. #include<algorithm>
  4. bool nprime[101];
  5. int a[26],i,j,k,n,ans,temp[25];
  6. struct node
  7. {
  8.         int list[25];
  9. }res[9801];
  10. bool cmp(node s,node t)
  11. {
  12.         return memcmp(s.list,t.list,sizeof(res[0].list))<0;
  13. }
  14. void calc(int s)
  15. {
  16.         int i;
  17.         for (i=1;i<=a[0];i++)
  18.         {
  19.                 temp[i-1]=0;
  20.                 while (s%a[i]==0)
  21.                 {
  22.                         s/=a[i];
  23.                         temp[i-1]++;
  24.                 }
  25.         }
  26. }
  27. int main()
  28. {
  29.         a[0]=0;
  30.         memset(nprime,false,sizeof(nprime));
  31.         for (i=2;i<=100;i++)
  32.                 if (!nprime[i])
  33.                 {
  34.                         a[++a[0]]=i;
  35.                         if (i<=10)
  36.                                 for (j=i*i;j<=100;j+=i)
  37.                                         nprime[j]=true;
  38.                 }
  39.         n=0;
  40.         for (i=2;i<=100;i++)
  41.         {
  42.                 calc(i);
  43.                 for (j=2;j<=100;j++)
  44.                 {
  45.                         for (k=0;k<a[0];k++)
  46.                                 res[n].list[k]=temp[k]*j;
  47.                         n++;
  48.                 }
  49.         }
  50.         std::sort(res,res+n,cmp);
  51.         ans=0;
  52.         for (i=j=0;;)
  53.         {
  54.                 ans++;
  55.                 while (j<n&&!memcmp(res[i].list,res[j].list,sizeof(res[0].list))) j++;
  56.                 if (j==n) break;
  57.                 i=j;
  58.         }
  59.         printf("%d\n",ans);
  60.         return 0;
  61. }

 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter