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

# TOJ 3
## 題目
https://toj.tfcis.org/oj/pro/3/
有 $t$ 筆測資，每筆測資包含兩個數 $a, b$，求 $a, b$ 的最大公因數

## 解法 By Koios1143
### 想法
可以模擬輾轉相除法求解，詳細過程可以參考講義內容。

### 程式碼

//By Koios1143
#include<iostream> 
using namespace std;
int gcd(int n,int m){
	if(n%m == 0){
		return m;
	}
	return gcd(m, n%m);
}
int main(){
	int t,a,b;
	cin>>t;
	while(t--){
		cin>>a>>b;
		cout<<gcd(a,b)<<"\n";	
	}
	return 0;
}

### 複雜度分析
證明我不知道怎麼證QQ ，不過每筆測資時間複雜度為 $O(log\ {min(a,b)})$

# TOJ 513
## 題目
https://toj.tfcis.org/oj/pro/513/
給兩個以 24 進位制表示的時間，包含小時以及分鐘，分別表示開始以及結束的時間，其中保證兩者之間間隔不會超過 24 小時，但是可能跨天，求兩個時間的間隔是幾小時幾分。

## 解法 By Koios1143
### 想法
分別算出兩者時間轉換成分鐘，這樣一來如果說結束時間比開始時間來的短，表示過了一天，再加上 $24*60$ 分鐘
最後只需要獲得間隔再轉成小時以及分鐘即可

### 程式碼

//By Koios1143
#include<iostream>
using namespace std;
int main(){
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	int start=a*60+b;
	int end=c*60+d;
	if(end-start<0){
		end+=24*60;
	}
	int res=end-start;
	cout<<"totally "<< res/60 <<" hours and "<< res%60 <<" minutes.\n";

	return 0;
}

### 複雜度分析
時間複雜度可記為 $O(1)$

# UVa412
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?412
給一個集合 $S$ ，從中任意取兩數 $p, q$
其中該集合所有 $p, q$ 對數記作 $A$， $p, q$ 互質的數量記作 $B$
求 $\sqrt{6*\frac{A}{B}}$ 四捨五入到小數點後第 $6$ 位

## 解法 By Koios1143
### 想法
這裡可以用很暴力的作法完成他
如果兩個數互質，那兩者的最大公因數一定是 $1$
那麼接下來暴力去看看每一組是不是互質，記錄下來即可

### 程式碼

//By Koios1143
#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;
int gcd(int n, int m){
	if(n%m == 0){
		return m;
	}
	return gcd(m, n%m);
}
int main(){
	int n;
	while(cin>>n && n){
		int arr[55];
		for(int i=0 ; i<n ; i++){
			cin>>arr[i];
		}
		int a=0,b=0;
		for(int i=0 ; i<n ; i++){
			for(int j=i+1 ; j<n ; j++){
				a++;
				if(gcd(arr[i], arr[j]) == 1)
					b++;
			}
		}
		if(b==0)
			cout<<"No estimate for this data set.\n";
		else
			cout<<fixed<<setprecision(6)<<sqrt((double)(a*6.0/b))<<"\n";
	}
	return 0;
}

# UVa12468
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?12468
有一台電視共有 $100$ 臺頻道，由 $0$~$99$，並且是環狀的，也就是說我可以從 $0$ 轉到第 $99$，反之亦同
現在要從頻道 $A$ 轉到頻道 $B$，每次只能轉一臺，正向或是逆向都可，求最少的轉移數

## 解法 By Koios1143
### 想法
分別算出正著轉以及逆著轉所需的移動次數，取最小值即可
當我從 $0$ 轉到 $99$
1. 正轉
$99-0 = 99$
2. 逆轉
$0-99+100 = 1$

因為是環，所以當我轉到變成負數，只要在加上 $100$ 就可以回到應該到的位置上了

### 程式碼

//By Koios1143
#include<iostream>
using namespace std;
int main(){
	int a,b;
	while(cin>>a>>b){
		if(a==-1 && b==-1)
			break;
		int forward = b-a;
		int reverse = a-b;
		if(forward<0)
			forward+=100;
		if(reverse<0)
			reverse+=100;
		cout<<min(forward, reverse)<<"\n";
	}
	return 0;
}

### 複雜度分析
每筆測資時間複雜度為 $O(1)$

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