UVa00524 Prime Ring Problem

題目連結

---

• ❗️ 題意
  給定數字n，代表利用1~n的數字圍成一個環，並以1當成出發點，連續的數字加起來一定要是質數(包括最後一個數字與1)，請輸出所以可能的組合。

---

• ✔️ 題解
  很明顯這題就是枚舉，我們只先建出一個質數表，只要建到31即可(n最大16，其中最大的質數就是15+16=31)，我們再利用backtracking的方式，維護一個vector，當目前的最後一個與要新加入的數字和為質數時就將其加入，並在當vector的長度為n時，確認最後一個與第一個數字的和是否是質數，再決定是否是合法的序列。
  其中，我們可以注意到，因為我們組出來的序列一定會是「奇偶奇偶奇偶奇偶…」，若n是奇數時，最後一個數字一定也會是奇數，結尾的奇數(至少3)加開頭的1一定是一個大於2的偶數，而大於2的偶數都不是質數，也就是說我們沒有辦法組合出任何一個序列，因此當n是奇數時是沒有答案的。

---

• 💻 程式碼

  160ms

  #include <bits/stdc++.h>
  using namespace std;
  
  
  vector<bool> prime_table(){
  	vector<bool> p(35, true);
  	p[0] = p[1] = false;
  	for(int i = 2; i < 35; i++){
  		if(p[i]){
  			for(int j = i * i; j < 35; j += i){
  				p[j] = false;
  			}
  		}
  	}
  	return p;
  }
  bool used[20];
  int n;
  vector<int>v;
  vector<bool>p;
  void dfs(){
  	if(v.size() == n && p[v.back() + 1]){
  		for(int i = 0; i < n; i++){
  			if(i == 0)
  				cout << v[i];
  			else
  				cout << " " << v[i];
  		}
  		cout << '\n';
  		return;
  	}
  	for(int i = 2; i <= n; i++){
  		if(!used[i]){
  			if(p[v[v.size() - 1] + i]){
  				v.emplace_back(i);
  				used[i] = true;
  				dfs();
  				v.pop_back();
  				used[i] = false;
  			}
  		}
  	}
  
  }
  int main(){
  	p = prime_table();
  	int kase = 0;
  	while(cin >> n){
  		memset(used, false, sizeof(used));
  		v.clear();
  		v.emplace_back(1);
  		used[1] = true;
  		if(kase)
  			cout << '\n';
  		cout << "Case " << ++kase << ":\n";
  		if((n & 1) == 0)
  			dfs();
  	}
  }

  在題目上沒提到連續兩個case間要換行🤔

---

• 🧠 心得
  昨天社團請了外部講師來講數論這個主題，講到後來我真的差點瘋了，後半部分真的完全聽不懂，有一半時間都在看著投影片發呆，剛好我又坐在最前面，超級尷尬的。高中時我一直自認為數學還不錯，上了大學後才發現自己的數學其實根本就不太好QQ，要多加油了～

---