# UVa題庫
歡迎光臨!
這是自學C++打算考到APCS 4級自學筆記 - UVa刷題篇
@2025 / 10 /28 HarryChen
{%preview https://hyc.eshachem.com/ %}
> 但UVa有些題目還是建議用python寫，真的快很多(打字速度)。
---
## 00494 - Kindergarten Counting Game
:::info
https://zerojudge.tw/ShowProblem?problemid=a011
:::
### 題目
算一算每行有幾個字（word）。
Word的定義是連續的字元（letter: A~Z a~z）所組成的字。
### 輸入說明:
一段文字(string)
### 輸出說明:
字數(int)
### 解題絲路
不是單純遇到空白拆開就好，有可能遇到以下情況:
> Hello! 123 123 World.
這樣一樣是只有一個"word"而已，所以要每個區塊都進去看一下。
透過isWord來控制現在位置，如果現在遇到字母，就是true，如果遇到不是字母的就是false。
cnt++ 的條件是: 從flase轉變成true時要++。
```cpp=
#include <bits/stdc++.h>
#define io ios::sync_with_stdio(0); cin.tie(0);
using namespace std;
bool isLetter(char c) {
return (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z');
}
int main() {
io;
string s;
while (getline(cin, s)) {
int cnt = 0;
bool inWord = false;
for (char c : s) {
if (isLetter(c)) {
if (!inWord) {
cnt++;
inWord = true;
}
} else {
inWord = false;
}
}
cout << cnt << '\n';
}
}
```
## 10055 - Hashmat the Brave Warrior
:::info
https://zerojudge.tw/ShowProblem?problemid=a012
:::
### 題目
Hashmat是一個勇敢的將領，他帶著年輕的士兵從這個城市移動到另一個城市與敵人對抗。在打仗之前他會計算己方與敵方士兵的數目差距，來決定是要開打或不開打。Hashmat 的士兵數絕不會比敵人的士兵數大。
### 輸入說明:
每組測試資料1列，有2個整數，代表Hashmat及敵人的士兵數或反之。這些數不會超過2
63
。
### 輸出說明:
對每組測試資料請輸出Hashmat與敵人士兵數目的差（正數）。
### 解題絲路
主要在考資料結構的認識(long long)以及 **不定個數輸入** 這件事
> input until EOFerror
```cpp=
#include <bits/stdc++.h>
#define io ios::sync_with_stdio(0); cin.tie(0);
using namespace std;
int main() {
io;
long long a,b;
while (cin >> a>>b){
cout << abs(a-b)<< '\n';;
}
}
```
## 12149 - Feynman
:::info
https://zerojudge.tw/ShowProblem?problemid=a111
:::
### 題目
費曼 (Richard Phillips Feynman) 是一個有名的美國物理學家及諾貝爾物理獎得主。他主攻理論物理並倡導量子電腦。他曾訪問南美十個月，在那兒演講並享受熱帶生活。他 的成名作「別鬧了，費曼先生」及「你管別人怎麼想」中也包含了他在赤道以南的經歷。
他一生的嗜好是解及建立謎題、鎖、及密碼。最近，曾在1949年接待費曼的一位南美老農夫找到一些據信屬於這位年輕物理學家的筆記。在這些有關介子及電磁學的筆記中，夾 有一張餐巾紙，上寫有個簡單的謎題：「在一個 𝑁 × 𝑁 的方格中含有幾個不同的正方形？」
下面重現了該餐巾紙上的圖，顯示 𝑁=2 時答案為 5。
### 輸入說明:
輸入有若干筆測資，每筆一行，含有一個整數 𝑁，代表方格的邊長 (1 ≤ 𝑁 ≤ 100)。
輸入的結束以含有一個零的一行表示。
### 輸出說明:
對於每筆測資，你的程式須輸出該筆測資一共包含幾個不同的正方形於一行。
### 解題絲路
考數學。
> 公式是 $n^2$+$(n-1)^2$+...+$1^2$
```cpp=
#include <bits/stdc++.h>
#define io ios::sync_with_stdio(0); cin.tie(0);
using namespace std;
int main() {
io;
long long a,b;
while (cin >> a){
if (a == 0)break;
int cnt =0;
for (int i=1;i<=a;i++)cnt += pow(i,2);
cout << cnt << '\n';
}
}
```
## 12015 - Google is Feeling Lucky
:::info
https://zerojudge.tw/ShowProblem?problemid=a130
:::
### 題目
Google 為最有名的網路搜尋引擎之一，它也提供許多網路服務與產品。在它的搜尋首面上有一個有趣的按鈕「好手氣」吸引了我們的目光。這個功能讓使用者跳過搜尋結果頁面而直接進入排名最高的頁面。真是省時又好用！
問題是，當按下「好手氣」時到底會出現哪一個頁面？Google 有個不錯的方式來處理。為了簡化問題，假設 Google 為每個頁面設定了一個整數的相關度。相關度最高的頁面就會中選。如果平分，所有的相關度最高的頁面都有可能中選。
給你 10 個頁面及相關度，請選出所有可能成為「好手氣」的頁面。
### 輸入說明:
輸入有多筆測資。輸入的第一行有測資的筆數 T。
每筆測資中有 10 行以描述頁面及相關度。每行含有一個不含空白的字串代表頁面的網址及一個整數 Vi 代表該頁面的相關度。網址的長度介於 1 到 100 之間(含)。( 1 <= Vi <= 100)
### 輸出說明:
對於每筆測資，輸出可能中選的頁面網址。網址出現的順序與輸入相同。輸出格式請參考輸出範例。
### 解題絲路
要注意的是網站相關度mx是不定值，所以在讀取的同時，也要去找最大值是誰，這樣輸出時只要second==mx時就好。
因為會讀取兩個值，所以很適合用c++中的pair來存取。
> 因為會要根據pair.second來排序所以用vector來存。並注意sort寫法。
```cpp=
#include <bits/stdc++.h>
#define io ios::sync_with_stdio(0); cin.tie(0);
using namespace std;
int main() {
io;
int n;
cin >> n;
int t = 1;
while (t!=n+1){
vector<pair<string, int>> p(10);
int mx = 0;
for (int i=0;i<10;i++){
cin >> p[i].first >> p[i].second;
mx = max(mx, p[i].second);
}
sort(p.begin(),p.end(),[](auto &a, auto &b){
return a.second<b.second;
});
cout << "Case #" << t<< ":"<< '\n';
for (auto &x : p) {
if (x.second == mx){
cout << x.first << '\n';
}
}
t++;
}
}
```
## 00739 - Soundex Indexing
:::info
https://zerojudge.tw/ShowProblem?problemid=a131
:::
### 題目
Soundex 指數系統的開發是為了將發音或拼字相似的名字的編碼以方便取用。它被美國戶口普查局所採用，許多州也用它來為駕照編碼。你的任務是讀取一連串的名字，一個一 行，計算 Soundex 碼，並把名字和編碼寫到輸出，(每個名字一行)。
每個名字包含 1 到 20 個大寫字母 (ASCII 碼 65 到 90)，長度不到 20 個字元的名字後面不會補空白。因此名字只會有大寫字母。
如何產生 Soundex 碼：
Soundex 碼含有一個字母及其後的三位數字。其編碼規則如下：
1. 名字的第一個字母成為編碼中第一且唯一的字母。2. A, E, I, O, U, Y, W 及 H 等字母不列入編碼，但可以拆散兩個連續編碼 (參見下一條)。3. 其餘的字母都必需編碼，除非它緊跟在一個編碼相同的字母之後。4. Soundex 編碼表為：
Code
Key Letters and Equivalents
1
B, P, F, V
2
C, S, K, G, J, Q, X, Z
3
D, T
4
L
5
M, N
6
R
5. 所有名字的編碼都是一位字母加三位數字，不足的位數補 0。6. 第三位數字之後的編碼捨去。
### 輸入說明:
輸入檔包含名字的表列，每行一個。每個名字不會超過 20 個字元，只用到太寫字母。你的程式要持繼讀取名字直到偵測到檔尾。
### 輸出說明:
輸出檔要包含名字及 Soundex 編碼兩欄。輸入檔的第一行中要分別在第 10 及第 35 字元輸出 "NAME" 及 "SOUNDEX CODE"。在標題之後，名字和編碼要出現在第 10 和第 35 字元，每組一行。在最後一個名字的下一行的第 20 個字元要出現 "END OF OUTPUT" 。
### 解題絲路
這題題目有誤，除了題目的colum不用輸出
正確規則還有一條:
:::info
是母音的話忽略不計算，H、W的話要延續。
:::
舉個例子:**LUKASCHOWSKY**
| 字母 | 步驟 | 編碼 | 為何取這個值 |
| :-: | :--: | :--: | :----------------- |
| L | 首字母 | 保留 L | 第一個字母不改 |
| U | 母音 | - | 母音不編碼 |
| K | 子音 | 2 | K 屬於 2 群 |
| A | 母音 | - | 母音不編碼、重置連續性 |
| S | 子音 | 2 | 因為母音打斷，重新算一個 2 |
| C | 子音 | 2 | S 和 C 是連續同群，所以略過後者 |
| H | 特殊字母 | - | 不編碼但保留連續性 |
| O | 母音 | - | 打斷連續性 |
| W | 特殊字母 | - | 不編碼但保留連續性 |
| S | 子音 | 2 | 重新編一次 2 |
| K | 子音 | 2 | 同群連續，略過 |
| Y | 母音 | - | 結束 |
所以正解會如下:
```python=
d = {
1:['B', 'P', 'F','V'],
2:['C', 'S', 'K', 'G', 'J','Q', 'X', 'Z'],
3:['D', 'T'],
4:['L'],
5:['M', 'N'],
6:['R'],
7:['A','E','I','O','U']
}
li = []
while True:
try:
s = input()
tmp = [s[0],0,0,0]
idx = 1
lk = 0
for k in d:
if s[0] in d[k]:
lk = k
for i in range(1,len(s)):
if idx > 3:break
for k in d:
if s[i] in d[k] and k!=lk:
if k==7:
lk=0
break
else:
tmp[idx] = k
idx+=1
lk = k
break
li.append([s,tmp])
except:
break
print("NAME SOUNDEX CODE")
for op in li:
print(" ",op[0],end = "")
for i in range(25-len(op[0])):
print(" ",end = "")
for i in op[1]:
print(i,end = "")
print()
print(" END OF OUTPUT")
```
## 10931 - Parity
:::info
https://zerojudge.tw/ShowProblem?problemid=a132
:::
### 題目
整數
n
的「同位元」定義為：其二進位表示法中每位元的和再除以 2 的餘數。例如：21 = 101012 的二進位有三個 1，因此它的同位元為 3 (mod 2)，或 1。
在此，你要計算一個整數
1 ≤ I ≤ 2147483647
的同位元。
### 輸入說明:
輸入的每一行有一個整數I，而I = 0表示輸入結束，該行無需處理。
### 輸出說明:
對於輸入中的每個整I，你要印一行The parity of B is P (mod 2).
，其中B是I的二進位表示法。
### 解題絲路
```python=
def base_conver(s):
num = int(s)
if num == 0:
return "0"
li = []
while num >0:
li.append(str( num %2))
num//=2
return ''.join(reversed(li))
while True:
n = input()
if n == '0':break
s = base_conver(n)
t = 0
for i in s:
if i=='1':
t+=1
print(f'The parity of {s} is {t} (mod 2).')
```
## 10066 - The Twin Towers
:::info
https://zerojudge.tw/ShowProblem?problemid=a133
:::
### 題目
很久以前在一個古老師王國有兩座形狀不同的塔聳立在兩個不同的城市裡。塔是以圓形磁磚疊起來的。每塊磁磚的高度相同且半徑均為整數。因此，儘管兩座塔形狀不同，卻包 含了許多相同的磁磚。
然而在建塔的一千多年後，國王命令建築師移除某些磁磚好使兩座塔的形狀大小都相同，並且要維持可能的最大高度。磁磚的順序須與原始建築相同。國王認為這樣可以象徵兩 個城市的和諧與平等。他名之為「雙子星塔」。
現在，大約兩千年後，你被賦予一個更簡單的任務：給你兩座塔的描述，你只要找出可能的最大磁磚數。
### 輸入說明:
輸入有若干筆測資。每筆測資代表一對雙子星塔。
每筆測資的第一行有兩個整數 N1 及 N2 (1 <= N1, N2 <= 100) 代表兩座塔的磁磚數。下一行含有 N1 個正整數，代表第一座塔由上而下磁磚的半徑。下一行的 N2 個整數則是第二座塔由上而下磁磚的半徑。
N1 及 N2 為 0 代表輸入結束。
### 輸出說明:
對於每一對雙子星塔，輸出它的編號及每座塔所能保留的最大可能磁磚數。測資間請空一行。
### 解題絲路
如果你想要暴力解，這裡有一技:
我把字串A的子序列全部列出來，再來判斷，該子序列是否出現在B中
```bash
A = "ABC"
→ 子序列有：
"", "A", "B", "C", "AB", "AC", "BC", "ABC"
共 2³ = 8 個
```
但如果今天A的長度到20，就會有$2^{20}$個子序列要試!
此時就會爆炸，這時不妨試一下DP的寫法!
DP LCS的想法是，我一直去比較1、2、3:怎樣才是最長序列(最優解)
所以我們定義:
> dp[i][j] = LCS 的長度，當考慮 A 的前 i 個字、B 的前 j 個字時。
```python=
k = 1
while True:
a,b = map(int,input().split())
if a==0 and b == 0:break
s1 = list(map(int, input().split()))
s2 = list(map(int, input().split()))
dp = [[0]*(b+1) for _ in range(a+1)]
for i in range(a):
for j in range(b):
if s1[i] == s2[j]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
print(f'Twin Towers #{k}')
print(f'Number of Tiles : {dp[a-1][b-1]}')
k+=1
```
## 00948 - Fibonaccimal Base
:::info
https://zerojudge.tw/ShowProblem?problemid=a134
:::
### 題目
有名的費氏數列是以 0 和 1 開始，然後把最後的兩個數字相加以得到下一項。例如數列的第三項為 1 (1=1+0)，第四項為 2 (2=1+1)，第五項為 3 (3=2+1)，等等。
這個數列很重要且出現在我們生活及大自然的許多事物上。其中，你知道所有的正整數都可以用費氏數列中的不重覆的數字集合的和來代表嗎？例如：13 可以是集合 {13}, {5,8} 或{2,3,8} 的和，而 17 則可用 {1,3,13} 或 {1,3,5,8}來表示。即然每個數都有這個特性 (你要自己證證看嗎？) 這個數列可以用作表示數字的「底」。但如前所示，有些數字有多種表示法，這該怎麼辦呢？簡單，因為費氏數列中任兩個連續項的和就是下一項，所以只要加上一個限制：不得使用連續的項，那麼每個數字都有一個唯一的表示法。
有了這個認知後我們可以建立一個很酷的方式來表示任意正整數。我們一連串的 0 與 1來表示。例如：17 = 1 + 3 + 13 (記住不可以使用費氏數列中連續的項)，以 0 來表示 沒有用到的項，以 1 來表示有用到的項，由右至左排列。因此 17 = 100101. 詳情參閱圖 2。在這個表示法中，最左邊的那一位數一定是 1，不可以是 0。根據我們的限制，這種表示法中不可以出現相鄰的 1。我們這種表示法為「費氏進位」並以下列方式表示 17 = 100101 (fib).
問題
給你一組十進位的數字，你的任務是將它們以費氏進位輸出。
### 輸入說明:
輸入的第一行含有一個數字
N
，代表以下有幾個數字 ( 1 ≤ N ≤ 500)。
接下來有
N
行，每行有一個小於 100 000 000 的正整數。數字不一定按順序出現。
### 輸出說明:
對於
N
個整數中的每一個整數要用下列格式輸出一行，"DEC_BASE = FIB_BASE (fib)"。DEC_BASE 原始的十進位數字而 FIB_BASE 則是它的費氏進位表示法。詳情參閱範例輸出。
### 解題絲路
用貪心即可。
將費氏數列reverse後，能確保每次取得的都是最大值。
```python=
'''
這種寫法會使li大過頭，導致程式崩潰
def fb(n):
li = [1,1]
for _ in range(2,50+1):
li.append(li[-1]+li[-2])
return li[1:]
'''
def fb(n):
li = [1,2]
while li[-1] <= n:
li.append(li[-1]+li[-2])
li.pop()
return li
n = int(input())
for i in range(n):
a = int(input())
s = a
if a == 1:print(f'{a} = 1 (fib)')
else:
li = fb(a)
li.reverse()
ans = ''
for i in li:
if i<=a:
a-=i
ans+='1'
elif ans!='':
ans+='0'
print(f'{s} = {ans.lstrip("0")} (fib)')
```
## 12250 - Language Detection
:::info
https://zerojudge.tw/ShowProblem?problemid=a135
:::
### 題目
英文、西班牙文、德文、法文、義大利文及俄文為歐盟國家中最盛行的 6 種語言。左圖顯示英語人口在歐洲各國的密度。這些語言都有不同的字來表示英文的「HELLO」。例如 西班牙文中等同於英文「HELLO」的字是「HOLA」，而德文、法文、義大利文及俄文中意思為(或相近)「HELLO」的字依序為「HALLO」、「BONJOUR」、「CIAO」和「ZDRAVSTVUJTE」。
你在本題中的任務非常簡單。給你以上的幾個單字之一或是其他的單字，你需要辨識它是哪一種語言。
### 輸入說明:
輸入檔含有大約2000行的輸入。每行含有一個字串S。你可以假設所有的字母都是大寫英文字母，且字串的最大長度為14。輸入以僅含有一個「#」的一行作為結束，該行不需處理。
### 輸出說明:
除了最後一行以外，相對於每一行輸入都要有一行輸出。
這行輸出含有輸出的序號及語言名稱。如果輸入的字串是「
HELLO
HOLA
HALLO
BONJOUR
CIAO
ZDRAVSTVUJTE時，你要回報它是哪一種語言。如果輸入字串是這 6 個以外的字串則印出字串
UNKNOWN。所有的輸出字串也都是大寫。詳細的格式細節請參見範例輸出。
### 解題絲路
用python中的字典(dict)，C++中的關聯式容器(map)即可。
```cpp=
#include <bits/stdc++.h>
#define io ios::sync_with_stdio(0); cin.tie(0);
using namespace std;
int main() {
io;
map<string, string> lang = {
{"HELLO", "ENGLISH"},
{"HOLA", "SPANISH"},
{"HALLO", "GERMAN"},
{"BONJOUR", "FRENCH"},
{"CIAO", "ITALIAN"},
{"ZDRAVSTVUJTE", "RUSSIAN"}
};
string s;
int caseNum = 1;
while (cin >> s) {
if (s == "#") break;
if (lang.count(s))
cout << "Case " << caseNum++ << ": " << lang[s] << '\n';
else
cout << "Case " << caseNum++ << ": UNKNOWN\n";
}
return 0;
}
```
## 11827 - Maximum GCD
python的list讀取方式可以幫助我們更快完成這題。
```python=
import math
n = int(input())
for i in range(n):
li = list(map(int,input().split()))
mx = 1
for i in range(0,len(li)):
for j in range(i+1,len(li)):
mx = max(mx, math.gcd(li[i],li[j]))
print(mx)
```
## 11743 - Credit Check
### 題目
這些日子以來，使用信用卡在網路上購買東西已經變的司空見慣。
但是因為信用卡卡號比較長，很容易在輸入他們的時候打錯。
為了快速的識別錯誤，如數字打錯，大多數的電子商務網站都會用一種校檢演算法來確認信用卡卡號
一種較為流行的校檢演算法叫做 "Luhn"演算法 (Luhn algorithm)，它可以檢測任何一位元的錯誤及多位元錯誤：
1.從倒數第二個位元開始，將他們放到後面，並且加倍其他沒有移動的位元到另一個列表
2.把列表內的數字的位元加總(n)，再把被移到後面的數字加總(m)，在把兩個數加起來 (n+m)
3.如果這個數字的結尾是0，則信用卡卡號為合法的，反之則是不合法的。
這裡有個例子，以這組號碼為例 5181 2710 9900 0012:
1.把相對應的數字加倍後，放到另一個列表 (5 181 2710 9900 0012) :10，16，4，2，18，0，0，2。
2.把這些數的位元加起來得到 (1+0) + (1+6) + 4 + 2 + (1+8) + 0 + 0 + 2=25
沒有對應到的位元合為1+1+7+0+9+0+0+2 = 20 ， 所以最後的總和是 20 + 25 = 45。
3. 45不是以0結尾，故這組信用卡號並不合法。
對於這個問題，你需要寫一個根據 Luhn演算法的程式來確認輸入的信用卡號是否合法。
讀取輸入後:
1. 先比對是否完全一樣(yes)
2. 若不一樣，再移除所有空白來比對。
用python會超時所以用C++，邏輯也很簡單。
不過題目有說，偶數位$*2$後要分別加($10$=>$1$+$0$)，但其實就是$-9$。
什麼意思?
:::success
因為只要超過9的數字都要拆開加總，而拆開加總這件事其實就是-9的結果。
:::
> $10$: $1$+$0$=$10-9$=$1$
```cpp=
#include <bits/stdc++.h>
#define io ios::sync_with_stdio(false); cin.tie(0);
using namespace std;
int main() {
io;
int n;
cin >> n;
cin.ignore();
while (n--){
string a,s;
getline(cin,a);
int sum=0;
for (auto c: a)c==' '? s+="" : s+=c;
for (int i=0;i<16;i++){
int d = s[i] - '0';
if (i % 2 == 0) { // 偶數位（從右邊數）
d *= 2;
if (d > 9) d -= 9;
}
sum += d;
}
cout << (sum%10==0 ? "Valid" : "Invalid")<<'\n';
}
}
```
## 11734 - Big Number of Teams will Solve This
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
cin.ignore(); // 忽略換行
for (int i = 1; i <= t; i++) {
string team, judge;
getline(cin, team);
getline(cin, judge);
if (team == judge) {
cout << "Case " << i << ": Yes\n";
continue;
}
// 移除隊伍字串中的所有空白
string team_no_space;
for (auto c : team)
if (c != ' ') team_no_space += c;
if (team_no_space == judge)
cout << "Case " << i << ": Output Format Error\n";
else
cout << "Case " << i << ": Wrong Answer\n";
}
}
```
## 10298 - Power Strings
:::info
**使用KMP演算法中的LPS表。**
簡單來說就是透過 LPS（Longest Prefix Suffix）陣列(前綴)，來避免不必要的重複比較。與DP有著異曲同工之妙。
[KMP演算法](/dc6oWKyZTvKIHbXQlpW3Gg)
:::
這題就是要我們找: **重複n次的最長子字串s是重複幾次?** 也就是求n本身。
我們可以透過LPS表，因為LPS[i]表示P[0..i] 這段字串中，最長的「前綴 = 後綴」的長度。
而對整個字串來說：
設 `len = P.length()`
設 `lps_last = LPS[len - 1]`
那 `len - lps_last` 就代表 能形成循環的基本單位長度（pattern 長度）。
:::success
如果整個字串真的由某段字串重複組成，那麼：
```
n % (n - last) == 0
```
代表能完整拆成重複字串，此時答案必須是：
```cpp
n = len / (len - lps_last)
```
即代表整個字串P是由一個長度為`len - lps_last`的子字串，重複n次組成的。
:::
舉例：ababab
| 索引 | 字串 | LPS |
| -- | ------ | --- |
| 0 | a | 0 |
| 1 | ab | 0 |
| 2 | aba | 1 |
| 3 | abab | 2 |
| 4 | ababa | 3 |
| 5 | ababab | 4 |
所以：
```
len = 6
lps_last = 4
n = 6 / (6-4) = 3
```
6 剛好是 2 的 3 倍 → 代表 “ab” 重複 3 次，所以輸出 3。
```cpp=
#include <bits/stdc++.h>
using namespace std;
// 建立 LPS 陣列
vector<int> buildLPS(const string &P) {
int m = P.length();
vector<int> lps(m, 0);
int len = 0;
int i = 1; // 從 P[1] 開始計算
while (i < m) {
if (P[i] == P[len]) {
len++;
lps[i] = len;
i++;
} else {
if (len > 0) {
// 回頭找更短的 prefix/suffix
len = lps[len - 1];
} else {
// 直接為 0
lps[i] = 0;
i++;
}
}
}
return lps;
}
int main() {
while (true){
string P;
cin >> P;
if (P==".")break;
vector<int> lps = buildLPS(P);
int n = P.length();
int last = lps[n-1];
int basic = n-last;
if (basic != 0 && n % basic == 0)
cout << n / basic << "\n";
else
cout << 1 << "\n";
}
}
```
# 00106 - Fermat vs. Pythagoras
## 解題絲路 - 純數學
三迴圈會超時，所以只能借助數學的力量了:
```bash
# 先將原式改寫
x² + y² = z²
y² = z² − x² = (z − x)(z + x)
令 y² = A × B
# 則可以推導下列二式
A + B = (z−x)+(z+x)=2z
B − A = (z+x)-(z−x)=2x
# 互質性：因為gcd(x,y,z)=1，可推 gcd(A,B)=2。所以gcd(u,v)=1。
# 平方分解：由AB=y²得(2u)(2v)=y²⇒(y/2)²=uv.
'''
此時u 與v 互質，且乘積是完全平方。若兩互質正整數的乘積為完全平方，則每個因數必為完全平方
'''
B − A = 2m² − 2n² = 2(m² − n²)
= 2x → x = m² − n²
A + B = 2n² + 2m² = 2(m² + n²)
= 2z → z = m² + n²
```
:::success
根據上述推論我們可以得知:
任何 primitive triple (x, y, z) 都一定能寫成：
* x = m² − n²
* y = 2mn
* z = m² + n²
* 並且滿足：
m > n
(m − n) 為奇數
gcd(m, n) = 1
:::
---
題目中限制 z 必須小於等於 N。
當 $m^2$ 已經大於 N，不管 n 怎麼選，z 一定會超過 N，因此：
$m^2 <= N$
$m <= sqrt(N)$
所以我們的迴圈也只需要跑到int(sqrt(N)) + 1就好。
---
接下來題目要求的"非互質(x,y,z)"只要透過倍數擴展的方式求得就好:
non-primitive例如：
6,8,10 → 由 (3,4,5) ×2
9,12,15 → 由 (3,4,5) ×3
---
```python=
from math import gcd, sqrt
while True:
try:
N = int(input())
used = [False] * (N + 1)
A = 0
limit = int(sqrt(N)) + 1
for m in range(2, limit):
for n in range(1, m):
if ((m - n) % 2 == 1) and (gcd(m, n) == 1):
x = m*m - n*n
y = 2*m*n
z = m*m + n*n
if z > N:
break
A += 1
k = 1
while k*z <= N:
used[k*x] = True
used[k*y] = True
used[k*z] = True
k += 1
not_used = sum(1 for i in range(1, N+1) if not used[i])
print(A, not_used)
except:
break
```
Sign in with Wallet
Connect another wallet