ZeroJudge J242: Natural Number's Square Root

Given a positive integer N, express 'sqrt(N)' in the format 'a sqrt(b)', where both a and b are positive integers, a²b = N, and b has no factors that are perfect squares, meaning for any natural number x, x² does not divide b. For example: sqrt(12) = 2 sqrt(3), sqrt(15) = sqrt(15), sqrt(100) = 10.

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
Each test case consists of only one positive integer N (1 < N < 231).The output format should be 'a sqrt(b)', and note the following:
If a = 1, do not print a.
If b = 1, do not print sqrt(b).
Leave a space between a and sqrt, and no spaces elsewhere.
122 sqrt(3)
15sqrt(15)
10010

Thought Process

First, check if N is a perfect square. If pow(sqrt(N), 2) == N, it means N is a perfect square, so output sqrt(N) directly.

If N is not a perfect square, initialize two variables a = 1 and b = N, both of which need to be of type Long Long Int. Run a while loop, and inside it, run a for loop iterating through every perfect square. Declare a variable 'plus' initialized to 3, and write the for loop as follows: 'for (int i = 4; i <= N; i += plus)', and after each iteration of the loop, increment 'plus' by 2.

In the for loop, iterate only through perfect squares. Check if i is a factor of b. If i is a factor of N, then update b /= i and a *= sqrt(i). If no factors are found in the current while loop iteration, break out of the while loop.

If a != 1, output a followed by a space character. Then output sqrt(b) after the conditional statement.

Sample Code－ZeroJudge J242: Natural Number's Square Root

#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
Tags

Related Posts

Comments