#include<stdio.h>                 
#include<stdlib.h>              
#include<string.h>
#include<math.h>
char x[10000000];       
main()              
{              
 int a,b,c;
 int math[5200]={0};           
 int m=1;  
 math[0]=2;
 for(a=3;a<50000;a=a+2)/*5W*5W已經2.5E 無須建更大*/    
  {     
   int flag=0;     
   for(b=0;math[b]<=sqrt(a);b++)     
    {     
     if(a%math[b]==0)     
      {     
       flag=1;     
       break;     
      }     
    }     
    if(flag==0)     
     {     
      math[m]=a;     
      m++;     
     }     
  }
 while(gets(x)!=0)              
  {              
   a=strlen(x);
  if(x[0]=='0'&&strlen(x)==1) break;              
  int temp1=0,max=0;
  unsigned long long int ans[1001]={0},top=0;
  unsigned long long int ans2=1;
  for(c=0;c<a;c++)  
   {              
   if(x[c]<=57&&x[c]>=48)              
    temp1=temp1*10+x[c]-48;              
   else               
    {        
     ans[top]=temp1;
     top++;
     if(temp1>=max)
      max=temp1;
     temp1=0;
     }
   }    
   ans[top]=temp1;
   top++;
   if(temp1>=max)
      max=temp1;
   for(a=0;a<m&&math[a]<max;a++)
     {
      int flag=0;
       for(b=0;b<top;b++)
        {
        if(ans[b]%math[a]==0)
         {
          ans[b]/=math[a];
          flag=1;
         }
      /*   printf("%d ",ans[b]); */
        }
      /* printf(">>>=%d \n",math[a]); */
       if(flag==1)
        {
         ans2*=math[a];
         ans2=ans2%100000000;
         a--;
        }
     }
    for(a=0;a<top;a++)
     {
      ans2*=ans[a];
      ans2=ans2%100000000;
     }
    printf("%lld\n",ans2);
  }                 
 return 0;              
} 

用國中的方式去除還是WA 見鬼了=口= 不知哪裡有錯誤

用大數才會對 (我之前居然忘記這點xD) 

我沒有用大數寫...

但是TLE= =沒辦法驗證對不對...

大數版本

for(a=0;a<top;a++)
     for(b=a+1;b<top;b++)
      if(ans[a]==ans[b])
        ans[b]=1;
用這個來解決大於5萬的相同質數

不想用大數的輾轉..

我沒用大數的版本，

跟你們蠻類似的，

一開始跟你的寫法一樣＝　＝！

但後來發現，

根本不用造質數表來增加次方數，

而是每驗證那一個數字來把它質因數分解，

再來建它的質數表，

這樣總數不會超過１０００個！

那分解的部份 不用建表 要怎麼處理

(1) 跟基礎題庫的那題的話 可能會有問題吧 上面所說的"大"質數的話 你可能就必須多跑很多來分解它如果有100個"大質數"的話  就BOOM了 例如100個數 2147483647  . . . . 通通都是質數=口=+

(2)http://cat.nknush.kh.edu.tw/ZeroJudge/ShowProblem?problemid=d121

   跟我的方式一樣用建表的速度應該比較快，這題建表會快很多，在那題使用基礎題庫的因數分解會    　TLE (3s)

(3)想知道...交一下

那題我用因式分解，

1.3s有點久ˊˋ，

不過建表不用花很多時間嗎＝　＝？

你說的大質數不會超過１００個，

因為它的數小於int的範圍且最多１００個數字，

所以這個問題不用擔心會有１００個相異大質數啦＠＠。

100個數字的部份 每個都是相異的大質數 必定是100個數字都相乘

我是想說這種情況啦

建表的好處是說 我們在驗證質數的部份可以減少 例如為了減少次數一定會先%2==0看看
 之後for(a=3;a<?;a=a+2) 這樣去跑 不過9 15 21......明明不是質數你還要多跑?

在測資很多的情況下 這種多跑的迴圈次數  應該會造成跑很久

如果我要完全分解它 最慘的情況要跑到5萬左右 就跑奇數好了 2萬5

建表裡面的內容只有5200左右的質數

[雖然剛開始花了2萬5*(我用表建表 我也不知道他跑幾次)的次數 不過在之後都可以減少2萬的次數(最慘的情況)]

然後如果在50000的質數都無法除盡代表他必定是一個質數 或者是說 他有一個因數大於5萬

因為大於5萬的質數小於我的那個數 若它不是質數那麼它的因數一定落在5萬以內 

阿~~

測資有誤拉><~我堅持=ˇ=...

大數最終版!!

#include<stdio.h>                 
#include<stdlib.h>              
#include<string.h>
#include<math.h>
char x[10000000];       
main()              
{              
 int a,b,c,d;
 long long int math[5200]={0};           
 int m=1;  
 math[0]=2;
 for(a=3;a<50000;a=a+2)/*5W*5W已經2.5E 無須建更大*/    
  {     
   int flag=0;
   for(b=0;math[b]<=sqrt(a);b++)     
    {     
     if(a%math[b]==0)     
      {     
       flag=1;     
       break;     
      }     
    }     
    if(flag==0)     
     {     
      math[m]=a;     
      m++;     
     }     
  }
 while(gets(x)!=0)              
  {              
   a=strlen(x);
  if(x[0]=='0'&&strlen(x)==1) break;
  if(strlen(x)==0) continue;          
  long long int temp1=0,max=0;
  long long int ans[1001]={0},top=0;
  long long int ans2[101]={0}; ans2[0]=1;
  /*我不會內建的參數判斷 所以我用分析的*/
  for(c=0;c<a;c++)  
   {              
   if(x[c]<=57&&x[c]>=48)              
    temp1=temp1*10+x[c]-48;              
   else               
    {        
     ans[top]=temp1;
     top++;
     if(temp1>=max)
      max=temp1;
     temp1=0;
     }
   }
   ans[top]=temp1;
   top++;
   if(temp1>=max)
      max=temp1;
   /*國中交的除法 找一個數去做除 全部都除一次 但是4的話 可能/2 剩2 那麼會跑到3 所以要重跑一次*/
   for(a=0;a<m&&math[a]<max;a++)
     {
      int flag=0;
       for(b=0;b<top;b++)
        {
        if(ans[b]%math[a]==0)
         {
          ans[b]/=math[a];
          flag=1;
         }
        }
       if(flag==1)
        {
         for(c=0;c<100;c++)
          ans2[c]*=math[a];
         for(c=0;c<100;c++)
          if(ans2[c]>=10)
           {
            ans2[c+1]=ans2[c+1]+ans2[c]/10;
            ans2[c]%=10;
           }
         a--;
        }
     }
    /*將同樣大的質數消掉*/
    for(a=0;a<top;a++)
     for(b=a+1;b<top;b++)
      if(ans[a]==ans[b])
        ans[b]=1;
    

/*大數乘法 原因 9 * 2147483647 用unsigned long long 也會暴 把剩下的大於5萬的質數 相乘起來*/
    for(a=0;a<top;a++)
     {
      int temp[100]={0},toptemp=0;
      int line[100]={0};
      if(ans[a]==1) continue;
      while(ans[a]%10!=0)
       {
        temp[toptemp]=ans[a]%10;
        toptemp++;
        ans[a]/=10;
       }
      for(c=0;c<100;c++)
       for(d=0;d<100;d++)
         {
          line[c+d]+=ans2[d]*temp[c];
         }
         for(c=0;c<100;c++)
          {
          if(line[c]>=10)
           {
            line[c+1]=line[c+1]+line[c]/10;
            line[c]=line[c]%10;
           }
            ans2[c]=line[c];
          }
     }
     /*輸出答案 為7位 但是答案可能為0 所以另外做判斷*/
    int  flag=0;
    for(a=7;a>=0;a--)
     if(ans2[a]!=0)
      {
       for(b=a;b>=0;b--)
        printf("%lld",ans2[b]);
        flag=1;
        printf("\n");break;
      } 
     if(flag==0)
       printf("0\n");
  }
 return 0;              
}  

/*所有情況都已經考慮 大數怎麼還是沒通過 哪尼(日語)=口=*/

我的方法就對啦@@...

不用用到大數那麼複雜拉= =!

感覺測資有誤...