# [函式] 公用函式、自定函式

## 找出最小的完全平方數

### 題目敘述
:::info
寫一個程式，輸入整數 k (0 < k ≤ 10)，找出 k 位數中，所有數字均為偶數的完全平方數中最小的一個數。例如當 k = 5，五位數中所有數字均為偶數的完全平方數中最小的數為 26244 (26244 = 1622) 。
:::

### 思考問題

> Q. 如何判斷某數是否為 ==k 位數==？
> Q. 如何判斷某數是否==每個數字均為偶數==？
> Q. 如何判斷某數是否為==完全平方數==？
> Q. 要用這三者的哪一個，作為迴圈的起始與終止條件？

### 解題指引
:::warning
- `可以一個一個數字找嗎？`
-> 不行。因為可能會爆時間複雜度！因為 k 最大是 10 ，最多要檢查 $10^9$ 個數字。此為多行輸入題，也就是可能會有多筆測資，就有可能超時。
- `要先遍歷所有「每個數字均為偶數」的數字，還是先遍歷所有「完全平方數」`
-> 前者還是要一個一個數字找，會TLE，但後者有些小技巧（後述）。
- `可以只找完全平方數嗎？`
-> 可以。不需要一個一個數字開根號喔！可以反向思考：「某數的平方介於 k 位數的範圍內，即為完全平方數」。
- `可以在 k 位數的範圍內找嗎？`
-> 可以。只要判斷 $10^n-1 <= 某數平方 < 10^n$ 次方即可。
- `可以不要設下限，從 1 開始找嗎？`
-> 可以。如果我們只設上限，只要在找「是否每個數字均為偶數」的同時，也同時判斷該數「是否為k位數」，就可以不要設下限，從1開始找，且不會有TLE的問題。
:::

### 範例程式碼

::: spoiler v1

#include <iostream>
#include <cmath>
using namespace std;

bool is_all_even(int n){
    while(n > 0){
        if(n%2)    return false;
        n = n/10;
    }
    return true;
}

int digit(int n){
    int d = 0;
    while(n > 0){
        d++;
        n = n/10;
    }
    return d;
}

int main(){
    int n;
    cin >> n;
    while(n--){
        int k;
        cin >> k;
        
        // int end = pow(10, k);
        long long end = pow(10, k);

        int i = 1;
        // 只要還沒超過範圍，且符合條件，就輸出並終止迴圈
        while(i*i < end){
            if(is_all_even(i*i) && digit(i*i) == k){
                cout << i*i << endl;
                break;
            }
            i++;
        }
    }
    
    return 0;
}

:::

以上曾經出錯的小細節：$10^{10}$ 會超過`int`型態的上限，因此需要改成`long long`。另外，由於10位數字中符合條件的結果，並沒有超過`int`型態的上限上限，我們也確認每個位數必然有解（有點後設），程式碼也可以修正如下：

::: spoiler v2

#include <iostream>
#include <cmath>
using namespace std;

bool is_all_even(int n){
    while(n > 0){
        if(n%2)    return false;
        n = n/10;
    }
    return true;
}

int digit(int n){
    int d = 0;
    while(n > 0){
        d++;
        n = n/10;
    }
    return d;
}

int main(){
    int n;
    cin >> n;
    while(n--){
        int k;
        cin >> k;
        
        int i = 1;
        // 不符合條件，就繼續往下找
        while(!(is_all_even(i*i) && digit(i*i) == k)){
            i++;
        }
        cout << i*i << endl;
    }
    return 0;
}

:::