演算法課程題解 - 基礎數論 3

TOJ 442

UVa 516

題目

http://domen111.github.io/UVa-Easy-Viewer/?516
給一個數字

$X$ 質因數分解後式，求

$X-1$ 的質因數分解式

解法 By Koios1143

想法

可以利用 stringstream 讀取輸入，取得所有數值就可以拿到

$X$ 以及

$X^{\prime }=X-1$
至於質因數分解的部分，我們可以藉由質數篩的過程當中紀錄每個數字第一次是被誰篩掉(也就是最小因數)
例如: 10 -> 2 9 -> 3 17 -> 17
如此一來，對於每個詢問

$X^{\prime }$ 每次先找到最小因數

$p$ ，紀錄當前的值

$X^{\prime }$ 可以被整除幾次，並且將

$X^{\prime }$ 除以

$p$，直到

$X^{\prime }$ 為

$1$ 的時候表示我們已經找完了

程式碼

//By Koios1143
#include<iostream>
#include<sstream>
#include<cmath>
const int MaxN = 32768;
int fact[MaxN], ans[MaxN][2];
using namespace std;
string s;
bool fir;
int x,n,a,b,p,cnt,px;
int main(){
	// 質數篩
	for(long long i=2 ; i<=MaxN ; i++){
		if(!fact[i]){
			fact[i]=i;
			for(long long j=i*i ; j<=MaxN ; j+=i){
				if(!fact[j]){
					fact[j]=i;
				}
			}
		}
	}
	
	while(getline(cin,s)){
		if(s=="0") break;
		fir=true; n=1; px=0;
		
		// 計算 X
		stringstream ss;
		ss<<s;
		while(ss>>x){
			if(fir) a=x;
			else{
				b=x;
				n*=pow(a,b);	
			}
			fir=!fir;
		}
		n--;
		
		// 質因數分解
		while(n!=1){
			p=fact[n];
			cnt=0;
			while(n%p==0){
				cnt++;
				n/=p;
			}
			ans[px][0]=p;
			ans[px][1]=cnt;
			px++;
		}
		
		for(int i=px-1 ; i>=0 ; i--){
			if(i!=px-1) cout<<" ";
			cout<<ans[i][0]<<" "<<ans[i][1];
		}
		cout<<"\n";
	}
	return 0;
}

複雜度分析

質數篩的複雜度為

$O(NloglogN)$
每筆測資計算

$X$ 時間複雜度約為

$O(\omega (X))$
每筆測資質因數分解時間複雜度約為

$O(\mathrm{\Omega }(X))$
每筆測資輸出時間複雜度約為

$O(\omega (X))$

其中，

$\omega (X)$ 表示

$X$ 的不同質因數個數。

$\mathrm{\Omega }(X)$ 表示

$X$ 的質因數個數
總時間複雜度約為

$O(NloglogN+2\omega (X)+\mathrm{\Omega }(X))$

UVa 10699

題目

http://domen111.github.io/UVa-Easy-Viewer/?10699
多筆輸入，每筆輸入包含一個正整數

$X$ ， 求

$X$ 有多少不同的質因數

解法 By Koios1143

想法

跟上一題類似，先透過質數篩找到每個數的最小質因數

$p$ ，再透過不斷的除以

$p$ 直到剩下

$1$ 為止，中間除去重複的以外，剩下就是答案

程式碼

//By Koios1143
#include<iostream>
const int MaxN = 1e6+5;
int fact[MaxN];
using namespace std;
int n,cnt,p;
int main(){
	for(long long i=2 ; i<=MaxN ; i++){
		if(!fact[i]){
			fact[i]=i;
			for(long long j=i*i ; j<=MaxN ; j+=i){
				if(!fact[j]){
					fact[j]=i;
				}
			}
		}
	}
	while(cin>>n && n){
		cnt=0;
		cout<<n<<" : ";
		while(n!=1){
			p=fact[n];
			cnt++;
			while(n%p==0){
				n/=p;
			}
		}
		cout<<cnt<<"\n";
	}
	return 0;
}

複雜度分析

質數篩的複雜度為

$O(NloglogN)$
每筆測資質因數分解時間複雜度約為

$O(\mathrm{\Omega }(X))$ 也有人說是約為

$O(logX)$
總時間複雜度約為

$O(NloglogN+\mathrm{\Omega }(X))$

UVa 10789

題目

http://domen111.github.io/UVa-Easy-Viewer/?10789
給一串字串

$S$ ，統計每個字元出現的次數，並輸出次數為質數的字元

解法 By Koios1143

想法

先建立質數表，統計過後查表即可

程式碼

//By Koios1143
#include<iostream>
using namespace std;
const int MaxN = 2002;
bool prime[MaxN];
string s;
int n,tbl[128];
string crt="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
int main(){
	for(int i=0 ; i<=MaxN ; i++){
		prime[i]=true;
	}
	prime[0] = prime[1] = false;
	for(long long i=2 ; i<=MaxN ; i++){
		if(prime[i]){
			for(long long j=i*i ; j<=MaxN ; j+=i){
				prime[j]=false;
			}
		}
	}
	cin>>n;
	for(int Case=1 ; Case<=n ; Case++){
		cin>>s;
		cout<<"Case "<<Case<<": ";
		for(int i=0 ; i<128 ; i++){
			tbl[i]=0;
		}
		for(int i=0 ; i<s.size() ; i++){
			tbl[s[i]]++;
		}
		bool out=false;
		for(int i=0 ; i<crt.size() ; i++){
			if(prime[tbl[crt[i]]] == true){
				cout<<crt[i];
				out=true;
			}
		}
		if(!out){
			cout<<"empty";
		}
		cout<<"\n";
	}
	return 0;
}

複雜度分析

建表時間複雜度為

$O(NloglogN)$
統計時間複雜度為

$O(len(S))$
總時間複雜度為

$O(NloglogN+len(S))$

UVa 11960

題目

http://domen111.github.io/UVa-Easy-Viewer/?11960
多筆測資，每筆測資包含一個正整數

$X$ ，求所有

$<=X$ 的正整數當中，因數個數最多的最大整數為何

解法 By Koios1143

想法

先做質因數分解，並且透過以下的想法可以找出每個數的因數個數

我們可以觀察

$24=2^3\ast 3$
其中的因數包含了

$1,2,3,4,6,8,12,24$
觀察一下會發現，這些因數都是由

$2$ 的某個小餘等於

$3$ 的次方乘上

$3$ 的某個小於等於

$1$ 的次方組合而成
也就是說我可以選擇要拿多少

$2$ 以及要拿多少

$3$ ，因數個數為

$(3+1)\ast (1+1)=8$
所以我們得到若

$X=a^p+b^q+c^r$ ，則

$X$ 的因數個數為

$(p-1)\ast (q-1)\ast (r-1)$

話說回來，利用上述的性質，加上質因數分解，就可以輕鬆求出每個數值的因數個數
而由於題目只需要所有

$<=X$ 的正整數當中，因數個數最多的最大整數，所以我們可以預先處理好所有人的答案

程式碼

//By Koios1143
#include<iostream>
const int MaxN = 1e6+5;
int fact[MaxN],ans[MaxN];
using namespace std;
int t,x;
int main(){
	for(long long i=2 ; i<=MaxN ; i++){
		if(!fact[i]){
			fact[i]=i;
			for(long long j=i*i ; j<=MaxN ; j+=i){
				if(!fact[j]){
					fact[j]=i;
				}
			}
		}
	}
	
	for(int i=1 ; i<=MaxN ; i++){
		// 後面要做乘法，所以預設值為 1
		ans[i]=1;
	}
	for(int i=2 ; i<=MaxN ; i++){
		int tmp=i;
		while(tmp!=1){
			int p=fact[tmp], cnt=0;
			while(tmp%p==0){
				tmp/=fact[tmp];
				cnt++;
			}
			ans[i]*=(cnt+1);
		}
	}
	
	// 預處理答案
	int n=2,m=ans[2];
	for(int i=2 ; i<=MaxN ; i++){
		if(ans[i]>=m){
			m=ans[i];
			n=i;
		}
		ans[i]=n;
	}
	
	cin>>t;
	while(t--){
		cin>>x;
		cout<<ans[x]<<"\n";
	}
	return 0;
}

複雜度分析

質數篩的複雜度為

$O(NloglogN)$
對所有數值做質因數分解，時間複雜度約為

$O(Nlog\mathrm{\Omega }(X))$
預處理答案的時間複雜度為

$O(N)$
每筆回答時間複雜度為

$O(1)$
總時間複雜度為

$O(NloglogN+Nlog\mathrm{\Omega }(X)+O(N)+O(t))$

tags: SCIST 演算法 題解