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

# TOJ 292
## 題目
https://toj.tfcis.org/oj/pro/292/
給三個整數 $A, B, C$ ，表示 $C$ 當前為 $A$ 進位制，求轉換成 $B$ 進位制的樣子。其中，我們只會在 $2$~$10$ 進位制之間轉換

## 解法 By Koios1143
### 想法
1. 先將 $C$ 想辦法換成我們熟悉的數字表示方式十進位
2. 統一從十進位轉換為其他進位制

而我們可以透過進位制本身的定義去想，例如 $216 = 2*10^2 + 1*10^1 + 6*10^0$。那麼，我們就可以將任意進位制的數值轉換成我們熟悉的樣子了。

要從十進位轉換成其他進位制，可以直接模擬短除法來達成。例如要將 $15_{10}$ 轉成二進位表示。
$15/2 = 7 ... 1$
$\ \ 7/2 = 3 ... 1$
$\ \ 3/2 = 1 ... 1$
那麼我們可以獲得 $1111_{2}$

### 程式碼

//By Koios1143
#include<iostream>
#include<cmath>
using namespace std;
int N_to_dec(int n, int num){
	int ans=0;
	for(int i=0 ; num ; i++, num/=10){
		ans+=(num%10)*pow(n,i);
	}
	return ans;
}
string dec_to_M(int m, int num){
	string ans="";
	for( ; num ; num/=m){
		ans = char(num%m + '0') + ans;
	}
	return ans;
}
int main(){
	int A,B,C;
	cin>>A>>B>>C;
	if(C==0)
		cout<<"0\n";
	else
		cout<<dec_to_M(B,N_to_dec(A,C))<<"\n";
	return 0;
}

### 複雜度分析
先轉換成十進位的時間複雜度為 $O(log_{10}{n})$
轉換成其他進位的時間複雜度為 $O(log_{10}{n})$
總時間複雜度約為 $O(log_{10}{n})$

# UVa 389
http://domen111.github.io/UVa-Easy-Viewer/?389
給一個字串 $S$ 以及兩個數字 $n, m$ ，表示 $S$ 是 $n$ 進位底下的表示方式，求轉成 $m$ 進位制的樣子。

## 解法 By Koios1143
### 想法
1. 先將 $S$ 想辦法換成我們熟悉的數字表示方式十進位
2. 統一從十進位轉換為其他進位制

做法與上一題是相同的，只是需要處理英文字母的部分
對於每個要轉換過去的單位數字 $p$
1. $p<10$
轉換後為 `char('0'+p)`
2. $p>=10$
轉換後為 `char('A'+p-10)`

### 程式碼

//By Koios1143
#include<iostream>
#include<cmath>
using namespace std;
int main(){
	string s;
	int n,m,res=0;
	while(cin>>s>>n>>m){
		res=0;
		for(int i=s.size()-1, j=0 ; i>=0 ; i--, j++){
			if(s[i]<='9'){
				res += (s[i]-'0')*pow(n,j);
			}
			else{
				res += (s[i]-'A'+10)*pow(n,j);
			}
		}
		string ans="";
		if(res==0){
			ans="      0";
		}
		else{
			for( ; res && ans.size()<=7 ; res/=m){
				int tmp=res%m;
				if(tmp>=10){
					ans = char(tmp-10+'A') + ans;
				}
				else{
					ans = char(tmp+'0') + ans;
				}
			}
		}
		if(ans.size() > 7){
			ans="  ERROR";
		}
		else{
			for(int i=ans.size() ; i<7 ; i++){
				ans=' ' + ans;
			}
		}
		cout<<ans<<"\n";
	}
	return 0;
}

### 複雜度分析
先轉換成十進位的時間複雜度為 $O(log_{10}{n})$
轉換成其他進位的時間複雜度為 $O(log_{10}{n})$
總時間複雜度約為 $O(log_{10}{n})$

# UVa 10473
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?10473
給一個字串 $S$ ，若 $S$ 是以 `0x` 開頭表示為 $16$ 進位，否則為 $10$ 進位
如果輸入 $16$ 進位，則輸出 $10$ 進位
如果輸入 $10$ 進位，則輸出 $16$ 進位

## 解法 By Koios1143
### 想法
1. 先將 $S$ 想辦法換成我們熟悉的數字表示方式十進位
2. 統一從十進位轉換為其他進位制

做法與上一題是相同的

### 程式碼

//By Koios1143
#include<iostream>
#include<cmath>
using namespace std;
int main(){
	string s;
	while(cin>>s){
		if(s[0]=='-'){
			break;
		}
		if(s.size()>2 && s[1] == 'x'){
			// hex
			long long ans=0;
			for(int i=s.size()-1, j=0 ; i>=2 ; i--, j++){
				if(s[i]<='9')
					ans+=(s[i]-'0')*pow(16, j);
				else
					ans+=(s[i]-'A'+10)*pow(16, j);
			}
			cout<<ans<<"\n";
		}
		else{
			// dec
			long long num = 0;
			for(int i=s.size()-1, j=0 ; i>=0 ; i--, j++){
				num += (s[i]-'0')*pow(10, j);
			}
			string ans="";
			for( ; num ; num/=16){
				int m = num%16;
				if(m>=10){
					ans = char(m-10+'A') + ans;
				}
				else{
					ans = char(m+'0') + ans;
				}
			}
			cout<<"0x"<<ans<<"\n";
		}
	}
	return 0;
}

### 複雜度分析
每種轉換方式的時間複雜度皆為 $O(log_{10}{n})$

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