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

79愛的鼓勵 1訂閱站台

作法 : DP

注意 : N=0 時 請輸出 0! 這個答案 ※ 這讓我吃好多WA on UVA

程式碼 1 : 記憶體過大

程式碼 2 : 利用二分搜尋 來減少記憶體量 來加快速度

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

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int n;
short int num[2750001]={0};
int sum[2750001]={0};
int last[10000002]={0};
void Divisors ()
{
  int a,b;
  for (a=2;a<=2750000;a++)
     {
       sum[a]=sum[a-1];
       if(a%2==0||num[a]!=0)
        {
            if(a%2==0)
                 sum[a]+=(sum[a/2]-sum[a/2-1])+1;
            else
                 sum[a]+=(sum[a/num[a]]-sum[a/num[a]-1])+1;
        }
       else sum[a]++;
      
       if(sum[a]<=10000001&&last[sum[a]]==0)
          last[sum[a]]=a;
       else break;
     }
}
void prime()
{  
 int a,b;
 for(a=3;a<1658;a=a+2)     
      if(num[a]==0)     
        {     
           for(b=3;a*b<=2750000;b=b+2)     
             num[a*b]=a;      /*Here*/
        }  
}
main()
{
 prime();
 Divisors ();
 int time=0;
 while(1) time++;
 while(scanf("%d",&n)==1&&n>=0)
    {
     printf("Case %d: ",++time);
     if(n==0) {printf("0!\n");continue;}
     if(last[n]!=0)
     printf("%d!\n",last[n]);
     else printf("Not possible.\n");
    }
 return 0;
}

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

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int n;
short int num[2703665]={0};
int sum[2703664]={0};
void Divisors ()
{
  int a,b;
  for (a=2;a<=2703663;a++)
     {
       sum[a]=sum[a-1];
       if(a%2==0||num[a]!=0)
        {
            if(a%2==0)
                 sum[a]+=(sum[a/2]-sum[a/2-1])+1;
            else
                 sum[a]+=(sum[a/num[a]]-sum[a/num[a]-1])+1;
        }
       else sum[a]++;
     }
}
void prime()
{  
 int a,b;
 for(a=3;a<1644;a=a+2)     
      if(num[a]==0)     
        {     
           for(b=3;a*b<=2703664;b=b+2)     
             num[a*b]=a;      /*Here*/
        }  
}
int indexL(int n,int top)  
{  
 int lower=0, mid, high=top-1;  
 int index=-1;  
    do   /*二分搜尋*/ 
    {  
      mid=(lower+high)/2;  
      if(sum[mid]<n)      lower=mid+1;  
      else if(sum[mid]>n) high=mid-1;  
      else                index=mid;  
    }  
    while(index==-1&&lower<=high);  
  return index;
}
main()
{
 prime();
 Divisors ();
 int time=0;
 while(scanf("%d",&n)==1&&n>=0)
    {
     printf("Case %d: ",++time);
     if(n==0) {printf("0!\n");continue;}
     int find=indexL(n,2703664);
     if(find!=-1)
     printf("%d!\n",find);
     else printf("Not possible.\n");
    }
 return 0;
}