演算法課程題解 - 基礎數論 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(logmin(a,b))$

TOJ 513

題目

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

解法 By Koios1143

想法

分別算出兩者時間轉換成分鐘，這樣一來如果說結束時間比開始時間來的短，表示過了一天，再加上

$24\ast 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\ast \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 演算法 題解