#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萬的相同質數
不想用大數的輾轉..
大數版本
for(a=0;a
for(b=a+1;b
if(ans[a]==ans[b])
ans[b]=1;
用這個來解決大於5萬的相同質數
不想用大數的輾轉..
我沒用大數的版本,
跟你們蠻類似的,
一開始跟你的寫法一樣= =!
但後來發現,
根本不用造質數表來增加次方數,
而是每驗證那一個數字來把它質因數分解,
再來建它的質數表,
這樣總數不會超過1000個!
我沒用大數的版本,
跟你們蠻類似的,
一開始跟你的寫法一樣= =!
但後來發現,
根本不用造質數表來增加次方數,
而是每驗證那一個數字來把它質因數分解,
再來建它的質數表,
這樣總數不會超過1000個!
那分解的部份 不用建表 要怎麼處理
(1) 跟基礎題庫的那題的話 可能會有問題吧 上面所說的"大"質數的話 你可能就必須多跑很多來分解它如果有100個"大質數"的話 就BOOM了 例如100個數 2147483647 . . . . 通通都是質數=口=+
(2)http://cat.nknush.kh.edu.tw/ZeroJudge/ShowProblem?problemid=d121
跟我的方式一樣用建表的速度應該比較快,這題建表會快很多,在那題使用基礎題庫的因數分解會 TLE (3s)
(3)想知道...交一下
我沒用大數的版本,
跟你們蠻類似的,
一開始跟你的寫法一樣= =!
但後來發現,
根本不用造質數表來增加次方數,
而是每驗證那一個數字來把它質因數分解,
再來建它的質數表,
這樣總數不會超過1000個!
那分解的部份 不用建表 要怎麼處理
(1) 跟基礎題庫的那題的話 可能會有問題吧 上面所說的"大"質數的話 你可能就必須多跑很多來分解它如果有100個"大質數"的話 就BOOM了 例如100個數 2147483647 . . . . 通通都是質數=口=+
(2)http://cat.nknush.kh.edu.tw/ZeroJudge/ShowProblem?problemid=d121
跟我的方式一樣用建表的速度應該比較快,這題建表會快很多,在那題使用基礎題庫的因數分解會 TLE (3s)
(3)想知道...交一下
那題我用因式分解,
1.3s有點久ˊˋ,
不過建表不用花很多時間嗎= =?
你說的大質數不會超過100個,
因為它的數小於int的範圍且最多100個數字,
所以這個問題不用擔心會有100個相異大質數啦@@。
那分解的部份 不用建表 要怎麼處理
(1) 跟基礎題庫的那題的話 可能會有問題吧 上面所說的"大"質數的話 你可能就必須多跑很多來分解它如果有100個"大質數"的話 就BOOM了 例如100個數 2147483647 . . . . 通通都是質數=口=+
(2)http://cat.nknush.kh.edu.tw/ZeroJudge/ShowProblem?problemid=d121
跟我的方式一樣用建表的速度應該比較快,這題建表會快很多,在那題使用基礎題庫的因數分解會 TLE (3s)
(3)想知道...交一下
那題我用因式分解,
1.3s有點久ˊˋ,
不過建表不用花很多時間嗎= =?
你說的大質數不會超過100個,
因為它的數小於int的範圍且最多100個數字,
所以這個問題不用擔心會有100個相異大質數啦@@。
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萬以內
那分解的部份 不用建表 要怎麼處理
(1) 跟基礎題庫的那題的話 可能會有問題吧 上面所說的"大"質數的話 你可能就必須多跑很多來分解它如果有100個"大質數"的話 就BOOM了 例如100個數 2147483647 . . . . 通通都是質數=口=+
(2)http://cat.nknush.kh.edu.tw/ZeroJudge/ShowProblem?problemid=d121
跟我的方式一樣用建表的速度應該比較快,這題建表會快很多,在那題使用基礎題庫的因數分解會 TLE (3s)
(3)想知道...交一下
那題我用因式分解,
1.3s有點久ˊˋ,
不過建表不用花很多時間嗎= =?
你說的大質數不會超過100個,
因為它的數小於int的範圍且最多100個數字,
所以這個問題不用擔心會有100個相異大質數啦@@。
100個數字的部份 每個都是相異的大質數 必定是100個數字都相乘
我是想說這種情況啦
建表的好處是說 我們在驗證質數的部份可以減少 例如為了減少次數一定會先%2==0看看
之後for(a=3;a
在測資很多的情況下 這種多跑的迴圈次數 應該會造成跑很久
如果我要完全分解它 最慘的情況要跑到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;
}
/*所有情況都已經考慮 大數怎麼還是沒通過 哪尼(日語)=口=*/
阿~~
測資有誤拉><~我堅持=ˇ=...
大數最終版!!
#include
#include
#include
#include
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
{
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
{
int flag=0;
for(b=0;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
for(b=a+1;b
if(ans[a]==ans[b])
ans[b]=1;
/*大數乘法 原因 9 * 2147483647 用unsigned long long 也會暴 把剩下的大於5萬的質數 相乘起來*/
for(a=0;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;
}
/*所有情況都已經考慮 大數怎麼還是沒通過 哪尼(日語)=口=*/
我的方法就對啦@@...
不用用到大數那麼複雜拉= =!
感覺測資有誤...
重測AC了 看來不用用到大數 如果有人需要答案是大數的 可用我上面的作法= =+