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

# TOJ 442

# UVa 516
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?516
給一個數字 $X$ 質因數分解後式，求 $X-1$ 的質因數分解式

## 解法 By Koios1143
### 想法
可以利用 stringstream 讀取輸入，取得所有數值就可以拿到 $X$ 以及 $X'=X-1$
至於質因數分解的部分，我們可以藉由質數篩的過程當中紀錄每個數字第一次是被誰篩掉(也就是最小因數)
例如: `10 -> 2` `9 -> 3` `17 -> 17`
如此一來，對於每個詢問 $X'$ 每次先找到最小因數 $p$ ，紀錄當前的值 $X'$ 可以被整除幾次，並且將 $X'$ 除以 $p$，直到 $X'$ 為 $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(\Omega(X))$
每筆測資輸出時間複雜度約為 $O(\omega(X))$

其中， $\omega(X)$ 表示 $X$ 的不同質因數個數。$\Omega(X)$ 表示 $X$ 的質因數個數
總時間複雜度約為 $O(NloglogN + 2\omega(X) + \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(\Omega(X))$ 也有人說是約為 $O(logX)$
總時間複雜度約為 $O(NloglogN + \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 * 3$
其中的因數包含了 $1, 2, 3, 4, 6, 8, 12, 24$
觀察一下會發現，這些因數都是由 $2$ 的某個小餘等於 $3$ 的次方乘上 $3$ 的某個小於等於 $1$ 的次方組合而成
也就是說我可以選擇要拿多少 $2$ 以及要拿多少 $3$ ，因數個數為 $(3+1)*(1+1)=8$
所以我們得到若 $X=a^p+b^q+c^r$ ，則 $X$ 的因數個數為 $(p-1)*(q-1)*(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\Omega(X))$
預處理答案的時間複雜度為 $O(N)$
每筆回答時間複雜度為 $O(1)$
總時間複雜度為 $O(NloglogN + Nlog\Omega(X) + O(N) + O(t))$

###### tags: `SCIST 演算法 題解`