[C/C++] ACM - 10539 - Almost Primes Numbers

這題的 long long 真是超級機車的, 遇到了一些奇怪的 coding 問題, submit 了大概快三十次才 AC 吧 = =

 

[問題一]

 

quicksort 裡的 compare function, 如果型態不是 long long,

 

以下兩種寫法都行, 只需對應參數的型態.

 

但如果是 long long 就只能用寫法二了, 真不知道為什麼? @@

 

寫法一 :

 int compare( const void *a, const void *b)
{  return (long long *)a - (long long*)b) ; }

 

寫法二 :

int compare(const void *a,const void *b)
{
   long long *c, *d;
   c=(long long *)a;
   d=(long long *)b;
  
   if(*c>*d)
      return 1;
   else if(*c==*d)
      return 0;
   else
      return -1;
} 

 

[問題二]

 

寫法一跟寫法二的意思是一樣的, 可是寫法一和寫法二 nonprime[] 裡存放的東西卻不一樣.

 

寫法一才是正確的, 寫法二卻不是?

 

寫法一:

long long temp;

long long nonprime[80080];

for (i = 0, k = 0; k < 80070; i++)
  {
  temp = prime[i];
  while ((temp *= prime[i]) <= 1e12)
    { nonprime[k++] = temp; }
  }

 

寫法二:

long long nonprime[80080];

for (i = 0, k = 0; k < 80070; i++)
  {
  nonprime[k] = prime[i]*prime[i];  // prime[i] * prime[i]  都會小於等於 1e12,  所以寫法一的迴圈也會跑  while (nonprimep[k] * prime[i] <= 1e12)
    {

    nonprime[k+1] = nonprime[k] * prime[k];

    k++; 

    }
   }

 

[心得]

 

突然發現 cout 可以正確的印出 long long 的值,

 

以後遇到 long long 的題目還是用 C++ 寫好了.