The first line gives the count n, and the second line gives n non-negative integers separated by spaces. For each x, find the largest integer r with r × r ≤ x. If x is a perfect square (r × r = x) print just r; otherwise print the two integers r and r + 1 that its square root lies between, separated by one space. One line per number. For example 16 → "4", 10 → "3 4", 0 → "0".
Input
1 ≤ n ≤ 1,000, 0 ≤ x ≤ 9,000,000,000,000,000 (9 × 10^15)
Output
n lines, each "r" or "r r+1"
Example 1 · stdin
5
0 10 16 99 1000000
stdout
0
3 4
4
9 10
1000
Example 2 · stdin
2
8999999847252241 8999999847252240
stdout
94868329
94868328 94868329
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
The trap is the floating-point square root. sqrt returns a double (about 16 significant digits) in every language. For x = k × k − 1 with k around 90 million, the true root is about k − 0.000000005, a gap smaller than the spacing of doubles there, so the result rounds to exactly k (second example: 94868329² − 1). Trusting Number.isInteger(Math.sqrt(x)) or (long)Math.sqrt(x) as is gives wrong answers. Python's math.isqrt(x) is an integer square root that never touches floats, so it is right as is; elsewhere take r from sqrt and fix it with integer products: while (r * r > x) r--; and while ((r + 1) * (r + 1) <= x) r++;. The numbers exceed 2.1 billion, so C, C++, Java and C# must read them as long (long long); in JS/TS/Craykon they stay below 2^53 (about 9.007 × 10^15), so r × r is exact. The two-way output fits a ternary: Python r if r * r == x else f"{r} {r + 1}" (the only language with that order), C-family and JS r * r == x ? … : …, Craykon too r * r == x ? r : r + " " + (r + 1). In C the two printf formats differ, so a plain if reads better.
Pythonmain.py · 6 lines
import mathn = int(input())for x in map(int, input().split()): r = math.isqrt(x) # 정수 제곱근: r*r <= x 인 가장 큰 r (실수를 거치지 않는다) print(r if r * r == x else f"{r} {r + 1}")
JavaScriptmain.js · 15 lines
const [n, ...xs] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);// Math.sqrt는 반올림된 실수라 큰 k*k-1에서 k가 나온다 → 정수로 다시 확인해서 고친다function isqrt(x) { let r = Math.floor(Math.sqrt(x)); while (r * r > x) r--; while ((r + 1) * (r + 1) <= x) r++; return r;}const out = xs.map((x) => { const r = isqrt(x); return r * r === x ? `${r}` : `${r} ${r + 1}`;});console.log(out.join("\n"));
TypeScriptmain.ts · 16 lines
import { readFileSync } from "node:fs";const [n, ...xs]: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);// Math.sqrt는 반올림된 실수라 큰 k*k-1에서 k가 나온다 → 정수로 다시 확인해서 고친다function isqrt(x: number): number { let r = Math.floor(Math.sqrt(x)); while (r * r > x) r--; while ((r + 1) * (r + 1) <= x) r++; return r;}const out: string[] = xs.map((x) => { const r = isqrt(x); return r * r === x ? `${r}` : `${r} ${r + 1}`;});console.log(out.join("\n"));
JavaMain.java · 26 lines
import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { // Math.sqrt는 double이라 큰 k*k-1에서 k가 나온다 → long으로 다시 확인해서 고친다 static long isqrt(long x) { long r = (long) Math.sqrt((double) x); while (r * r > x) r--; while ((r + 1) * (r + 1) <= x) r++; return r; } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine().trim()); StringTokenizer st = new StringTokenizer(br.readLine()); StringBuilder out = new StringBuilder(); for (int i = 0; i < n; i++) { long x = Long.parseLong(st.nextToken()); long r = isqrt(x); out.append(r * r == x ? String.valueOf(r) : r + " " + (r + 1)).append('\n'); } System.out.print(out); }}
C#Main.cs · 24 lines
using System;class Program{ // Math.Sqrt는 double이라 큰 k*k-1에서 k가 나온다 → long으로 다시 확인해서 고친다 static long Isqrt(long x) { long r = (long)Math.Sqrt(x); while (r * r > x) r--; while ((r + 1) * (r + 1) <= x) r++; return r; } static void Main() { Console.ReadLine(); foreach (string s in Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries)) { long x = long.Parse(s); long r = Isqrt(x); Console.WriteLine(r * r == x ? $"{r}" : $"{r} {r + 1}"); } }}
C++main.cpp · 24 lines
#include <cmath>#include <iostream>// std::sqrt는 double이라 큰 k*k-1에서 k가 나온다 → long long으로 다시 확인해서 고친다long long isqrt(long long x) { long long r = static_cast<long long>(std::sqrt(static_cast<double>(x))); while (r * r > x) r--; while ((r + 1) * (r + 1) <= x) r++; return r;}int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; long long x; std::cin >> n; for (int i = 0; i < n; i++) { std::cin >> x; long long r = isqrt(x); if (r * r == x) std::cout << r << '\n'; else std::cout << r << ' ' << r + 1 << '\n'; }}
Cmain.c · 23 lines
#include <math.h>#include <stdio.h>/* sqrt는 double이라 큰 k*k-1에서 k가 나온다 → long long으로 다시 확인해서 고친다 */long long isqrt(long long x) { long long r = (long long)sqrt((double)x); while (r * r > x) r--; while ((r + 1) * (r + 1) <= x) r++; return r;}int main(void) { int n; long long x; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%lld", &x); long long r = isqrt(x); if (r * r == x) printf("%lld\n", r); else printf("%lld %lld\n", r, r + 1); } return 0;}
Craykonmain.cray · 22 lines
// 수학.제곱근은 반올림된 실수라 큰 k*k-1에서 k가 나온다 → 곱해서 다시 확인하고 고친다정수제곱근(x){ r = Mathf.Floor(Mathf.Sqrt(x)); while (r * r > x) { r--; } while ((r + 1) * (r + 1) <= x) { r++; } return r;}n = Console.ReadLine().ToNumber();수들 = Console.ReadNumbers();foreach (x in 수들){ r = 정수제곱근(x); Console.WriteLine(r * r == x ? r : r + " " + (r + 1));}