Tìm |x-y|

Xem PDF
Tác giả:
jumptozero
Dạng bài
Điểm: 400 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho số nguyên dương \(x\).

Yêu cầu: Tìm số nguyên dương \(y\) thoả mãn 3 điều kiện sau:

  • \(y\ge 2\)

  • \(|x-y|\) đạt giá trị nhỏ nhất

  • Khi phân tích \(y\) ra thừa số nguyên tố, thì mỗi thừa số nguyên tố xuất hiện đúng \(2\) lần.

Sau khi tìm được \(y\) thoả mãn yêu cầu bài toán, in ra màn hình giá trị \(|x-y|\)

Input

  • Dòng thứ nhất chứa số \(T(1\le T\le 50)\) - thể hiện số testcase.

  • \(T\) dòng tiếp theo, mỗi dòng chứa số nguyên \(x(1\le x\le 10^{18})\)

Output

  • Ứng với mỗi testcase, in ra đáp án \(|x-y|\) cần tìm.

Example

Test 1

Input 
3
3
5
35
Output 
1
1
1
Note

  • Ứng với \(x=3\), ta tìm được \(y=4\). Vì \(4=2^2\) và \(|y-x|=1\) đạt giá trị nhỏ nhất.

  • Ứng với \(x=5\), ta tìm được \(y=4\). Vì \(4=2^2\) và \(|y-x|=1\) đạt giá trị nhỏ nhất.

  • Ứng với \(x=35\), ta tìm được \(y=36\). Vì \(36 = 2^2.3^2\) và \(|y-x|=1\) đạt giá trị nhỏ nhất

Bình luận


  • 15
    longkold00    3:48 p.m. 16 Tháng 10, 2021

    bài này chúng ta sẽ làm tròn a=sqrt(x). Ta nhận thấy a lúc này sẽ là 1 số đc khi phân tích thì các số nt chỉ xuất hiện 1 lần. ta sẽ kiểm tra các số xung quanh a 11 đơn vị (do sẽ luôn tồn tại 1 số nt or a thỏa mãn) + 1 biến res=LLONG_MAX để ghi lại đáp án.


    • -1
      mcsmuscle    10:53 p.m. 8 Tháng 2, 2022

      cám ơn anh nhiều


      • 5
        VoBaThongL921    5:04 p.m. 16 Tháng 10, 2021

        Thanks anh:) lúc đầu em không để ý cái dòng "Khi phân tích y ra thừa số nguyên tố, thì mỗi thừa số nguyên tố xuất hiện đúng 2 lần" mà chỉ nghĩ chắc chắn y phải là số chính phương, nên em chỉ xét 2 số chính phương gần nhất với căn của x thôi, chứ không để ý là phân tích số đó ra có được "mỗi thừa số nguyên tố xuất hiện đúng 2 lần" hay không ạ:>

        3 bình luận nữa