zerojudge c666. 質數乘積

題目在 https://zerojudge.tw/ShowProblem?problemid=c666

這題是結合質數和大數乘法, 把求出的質數連乘起來. 質數的算法請參考我的另一篇文章zerojudge b513. 判斷質數-商競103. 大數乘法則參考zerojudge a021. 大數運算. 兩篇程式剪貼一下就可以完成這題目.

程式先找出5000個質數, 然後根據測資n, 去做n個質數連乘, 為了加速計算, 我把算過的大數存在字串陣列裡, 就不用每個n都從頭開始計算.

//找出前5000個質數
	V.push_back(2);
	V.push_back(3);
	int index=6;
	int count=0;
	while(V.size()<5000){
		if(getNextPrime(index-1))
			V.push_back(index-1);

		if(getNextPrime(index+1))
			V.push_back(index+1);
		index+=6;
	}
	
        int n;
	while(scanf("%d",&n)!=EOF)
	{
		//若已知大數則直接印出
		if(n<big_number_index){
			printf("%s\n", big_number[n-1].c_str());
			continue;
		}

		char buffer[10];
		//從已知的大數開始算至測資要求的n個質數
		for(int i=big_number_index;i<n;i++){
			sprintf(buffer, "%d", V[i]);
			big_number[i]=MUL(big_number[i-1], string(buffer));
		}
		big_number_index=n;

		printf("%s\n", big_number[n-1].c_str());
	}

C++

先透漏給你知道,測資#3 n=877, 答案開頭是154181816302……, 測資#3如果AC, 後面應該也會AC, 除非是你哪個buffer爆了. 最後, n=5000時,答案字串長度是20975bytes, 這樣你知道buffer要設多大了吧!

完整程式如下.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

//儲存所有質數
vector <int> V;

//檢查v是否為質數
bool getNextPrime(int v){
	int max=sqrt(v);
	for(int i : V){
		if(i>max)  break;
		if(v%i==0)
			return false;
	}
	return true;
}

//儲存5000個大數
string big_number[5000]={"2","6","30", "210", "2310", "30030","510510"};
int big_number_index=7; //已知大數有7個


int MA[30000];
int MB[30000];
int MAB[30000];
char MUL_buffer[30000];

//計算大數a*b 並傳回
string MUL(string a, string b)
{
	memset(MAB, 0, sizeof(int)*30000);
	memset(MUL_buffer, 0, sizeof(char)*30000);
	int a_size=a.size();
	int b_size=b.size();

	//字串a轉數字
	int index=0;
	for(int i=a_size-1;i>=0;i--){
		MA[index++]=a[i]-'0';
	}

	//字串b轉數字
	index=0;
	for(int i=b_size-1;i>=0;i--){
		MB[index++]=b[i]-'0';
	}

	//直式相乘
	for(int i=0;i<=b_size;i++){
		int B=MB[i];
		for(int j=0;j<=a_size;j++){
			MAB[i+j]+=B*MA[j];
		}
	}

	//處理進位
	for(int i=0;i<a_size+b_size;i++){
		if(MAB[i]>=10){
			MAB[i+1]+=MAB[i]/10;
			MAB[i]%=10;
		}
	}

	//從左到右印出
	int buffer_index=0;
	bool first=true;
	for(int i=a_size+b_size;i>=0;i--){
		if(first){
			if(MAB[i]){
				MUL_buffer[buffer_index++]=MAB[i]+'0';
				first=false;
			}
			continue;
		}
		MUL_buffer[buffer_index++]=MAB[i]+'0';
	}
	//當從未印出即為0
	if(first){
		MUL_buffer[buffer_index++]='0';
	}
	MUL_buffer[buffer_index++]=0;
	return string(MUL_buffer);
}



int main(){

	//找出前5000個質數
	V.push_back(2);
	V.push_back(3);
	int index=6;
	int count=0;
	while(V.size()<5000){
		if(getNextPrime(index-1))
			V.push_back(index-1);

		if(getNextPrime(index+1))
			V.push_back(index+1);
		index+=6;
	}

	int n;
	while(scanf("%d",&n)!=EOF)
	{
		//若已知大數則直接印出
		if(n<big_number_index){
			printf("%s\n", big_number[n-1].c_str());
			continue;
		}

		char buffer[10];
		//從已知的大數開始算至測資要求的n個質數
		for(int i=big_number_index;i<n;i++){
			sprintf(buffer, "%d", V[i]);
			big_number[i]=MUL(big_number[i-1], string(buffer));
		}
    	        big_number_index=n;

		printf("%s\n", big_number[n-1].c_str());
	}
}

C++

zerojudge c666. 質數乘積

Archives

Categories