ZeroJudge J242: 自然數的平方根

輸入正整數 N，將「sqrt(N)」轉換成「a sqrt(b)」之格式，其中 a 與 b 都是正整數，a2b = N，且 b 的因數不為任何平方數，亦即，對任何自然數 x，x2 不能整除 b。例如：sqrt(12) = 2 sqrt(3)，sqrt(15) = sqrt(15)，sqrt(100) = 10。

範例測資

範例輸入範例輸出
每一組測試資料僅有 1 個正整數 N。1 < N < 231。輸出為「a sqrt(b)」，並注意：
1） 若 a = 1 則不印出 a。
2） 若 b = 1 則不印出 sqrt(b)。
3） 在 a 與 sqrt 之間留一空白，其餘均無空白。
122 sqrt(3)
15sqrt(15)
10010

解題思路

先判斷 N 是否為完全平方數，如果 pow(sqrt(N), 2) == N，代表 N 為完全平方數，直接輸出 sqrt(N) 即可。

如果 N 不是完全平方數，預設兩個變數 a = 1、b = N，兩個變數都需要 Long Long Int。跑一個 While迴圈，並且跑一個 For迴圈並跑每一個完全平方數，可以宣告一個變數 plus 為 3，並且將 For迴圈 寫成：「for (int i = 4; i<=N; i+=plus)」，並且在每一次迴圈結束之後將 plus += 2。

For迴圈 每次都只會跑到完全平方數，只要判斷 i 是否為 b 的因數，如果 i 為 N 的因數，則將 b /= i、a *= sqrt(i)，如果本次 While迴圈 沒有判斷到因數，則將 While迴圈 Break 掉。

如果 a != 1，就輸出 a 跟一個空格字元。在判斷式後面輸出 sqrt(b)。

範例程式碼－ZeroJudge J242: 自然數的平方根

#include <iostream>
#include <math.h>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    long long int N;
    cin >> N;
    if (pow(int(sqrt(N)), 2) == N) cout << sqrt(N) << "\n";
    else {
        long long int a = 1, b = N;
        bool stop = false;
        while (!stop) {
            stop = true;
            long long int plus = 3;
            for (long long int i = 4; i<=N; i+=plus) {
                if (b % i == 0) {
                    b /= i;
                    a *= int(sqrt(i));
                    stop = false;
                }
                plus += 2;
            }
        }
        if (a != 1) cout << a << " ";
        cout << "sqrt(" << b << ")\n";
    }
}

//ZeroJudge J242
//Dr. SeanXD
標籤

相關文章

發佈留言