Ước số phong thuỷ
Submit solution
Points:
4
Time limit:
1.0s
JAVA11
2.0s
Memory limit:
977M
JAVA11
488M
Author:
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG
x là một ước số phong thuỷ của n khi và chỉ khi n chia hết cho x và x+1.
Cho bạn một số n, hãy tìm toàn bộ ước số phong thuỷ của nó.
Input
- Dòng đầu tiên là số nguyên \(t (t \le 100)\) ứng với số bộ test.
- t dòng tiếp theo, mỗi dòng là 1 số \(n (1 \le n \le 10^{18})\) .
Output
- Với mỗi test, in ra tất cả các ước số phong thuỷ theo thứ tự tăng dần. Nếu không có giá trị nào, in ra -1.
Example
Input 1
4
35
40
50
60Output 1
-1
1 4
1
1 2 3 4 5Giải thích:
Test 1: 35 không có ước số phong thuỷ nào nên in ra -1.
Test 2: 40 chia hết cho cả 1 và 2 nên 1 là ước số phong thuỷ của 40. Tương tự với các trường hợp còn lại
Comments
có thuật toán chạy vớ vẩn đến 1e4 vx ac, hehe
test íu nên lách được thời gian nhanh vãi, chứ code ban đầu kia chặt thế thì vẫn AC thôi
Cơ mà bài này chị Ngọc anh sinh test vẫn hơi yếu nhá v: , cho quả test supper chặt tí
Gợi ý : n chia cho x và (x + 1) , tương đương n cũng chia hết cho x (x + 1) , nhiệm vụ giờ chỉ cần tìm các bội của x (x + 1) trong thời gian O(n ^(1/3)) là AC