摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法 : 建表

普通的DP建表 我就不說了

在此提供 DP 建表...先利用篩法得到某數必有的質因數

之後只要除那個質因數就能利用之前所建出來的數值去+

就可以減少運算的次數

不過速度仍然不夠快... (除非直接把值存在陣列裡面)

/***********************************************************/

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
short int num[500001]={0};
int sopf[500001]={0};
char lsopf[500001]={0};
void Divisors ()
{
  int a,b;
  for (a=2;a<=500000;a++)
     {
       if(a%2==0||num[a]!=0)
        {
            if(a%2==0)
                 sopf[a]=sopf[a/2]+2;
            else
                 sopf[a]=sopf[a/num[a]]+num[a];
        }
       else sopf[a]=a;
      
       if(a!=sopf[a]) lsopf[a]=lsopf[sopf[a]]+1;
       else lsopf[a]=1;
     }
}
void prime()
{  
 int a,b;
 for(a=3;a<=707;a=a+2)     
      if(num[a]==0)     
        {     
           for(b=3;a*b<=500000;b=b+2)     
             num[a*b]=a;      /*Here*/
        }  
}
main()
{
 prime();
 Divisors ();
 int n,m,t,time=1,a;
 scanf("%d",&t);
 while(t--)
     {
       int max=0;
       scanf("%d %d",&n,&m);
       if(n>m)
         {
           int temp=n;
           n=m;
           m=temp;
         }
       for(a=n;a<=m&&max!=14;a++)
          if(lsopf[a]>max) max=lsopf[a];
       printf("Case #%d:\n%d\n",time++,max);
     }
 return 0;
}