題目在 https://zerojudge.tw/ShowProblem?problemid=e293.
這題目寫了一堆根本也不用看, 簡單的講就是要把5000位的大數, 找出所有小於100的質數.
計算質數的程式可以參考另一篇zerojudge b513. 判斷質數-商競103.小於100的質數有25個, 因為題目的時間限制才0.4秒, 就不要花時間去計算質數, 直接寫在程式裡就好.
我用大數除以每個質數的餘數是否為0, 來檢查是否為質因數. 為了加快速度, 我把大數轉成long long型態來求餘比較快. 大數則放在global 變數也可省去參數的傳遞時間.
string BigNumber;
long long MOD(long long b){
int L=BigNumber.length();
long long a1=BigNumber[0];
for(int i=1;i<L;i++){
a1=a1*10+BigNumber[i];
if(a1<100000000000000000)
continue;
a1=a1%b;
}
return a1;
}
現在可以25個質數一個一個檢查. 但是用大數來做25遍太慢了, 一定會TLE. 只有2和5這兩個質數檢查非常快,所以可以分開做. 其他23個質數, 我分成三組來檢查. 第一組是{3,7,11,13,17,19,23,29,31,37},把所有質數乘起來為742073813481, 這數字存於long long不會爆. 然後用上面的方法求餘數, 根據數學原理,如果大數的質因數有在這組質數裡, 那也會存在這餘數裡. 所以就把求得的餘數取代大數來計算就可以很快查出質因數.
void stage1(){
long long prime[]={3,7,11,13,17,19,23,29,31,37};
long long b = MOD(742073813481);
if(b==0){ //剛好這組所有的質數都是質因數
for(long long p:prime){
P.insert(p);
}
return;
}
//每個質數去算是不是質因數
for(long long p:prime){
if(b%p==0){
P.insert(p);
}
}
return;
}這樣做三次, 第二組我用{41,43,47,53,59,61,67}, 質數相乘為1058967640189, 把第一步程式改一改就好了.
void stage2(){
long long prime[]={41,43,47,53,59,61,67};
long long b = MOD(1058967640189);
if(b==0){ //剛好這組所有的質數都是質因數
for(long long p:prime){
P.insert(p);
}
return;
}
//每個質數去算是不是質因數
for(long long p:prime){
if(b%p==0){
P.insert(p);
}
}
}
第三組我就不寫了. 至於為什麼分三組, 不分兩組或四組? 我就測出來分三組最快呀. AC時間僅0.2秒.
完整程式如下.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <set>
using namespace std;
string BigNumber;
long long MOD(long long b){
int L=BigNumber.length();
long long a1=BigNumber[0];
for(int i=1;i<L;i++){
a1=a1*10+BigNumber[i];
if(a1<100000000000000000)
continue;
a1=a1%b;
}
return a1;
}
set <int> P;
void stage1(){
long long prime[]={3,7,11,13,17,19,23,29,31,37};
long long b = MOD(742073813481);
if(b==0){ //剛好這組所有的質數都是質因數
for(long long p:prime){
P.insert(p);
}
return;
}
//每個質數去算是不是質因數
for(long long p:prime){
if(b%p==0){
P.insert(p);
}
}
return;
}
void stage2(){
long long prime[]={41,43,47,53,59,61,67};
long long b = MOD(1058967640189);
if(b==0){ //剛好這組所有的質數都是質因數
for(long long p:prime){
P.insert(p);
}
return;
}
//每個質數去算是不是質因數
for(long long p:prime){
if(b%p==0){
P.insert(p);
}
}
}
void stage3(){
long long prime[]={71,73,79,83,89,97};
long long b = MOD(293391909323);
if(b==0){ //剛好這組所有的質數都是質因數
for(long long p:prime){
P.insert(p);
}
return;
}
//每個質數去算是不是質因數
for(long long p:prime){
if(b%p==0){
P.insert(p);
}
}
}
char buffer[5001];
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%s",buffer);
P.clear();
BigNumber=string(buffer);
//檢查最後一位, 來確定是否為2或5的倍數
int check2 = BigNumber[BigNumber.length()-1]-'0';
if(check2%2==0)
P.insert(2);
if(check2==0 || check2==5)
P.insert(5);
//字串轉數字
for(int i=0;i<BigNumber.length();i++){
BigNumber[i]=BigNumber[i]-'0';
}
//分三段檢查質因數
stage1();
stage2();
stage3();
if(P.size()==0){
printf("Terrible Silence...\n");
}else{
for(int n:P){
printf("%d ",n);
}
printf("\n");
}
}
}