trang chủ / đề bài / icpcwf13_d

Thừa số

Đề bài

Mô tả

Định lý cơ bản của số học phát biểu rằng mọi số nguyên lớn hơn 1 đều biểu diễn được một cách duy nhất thành tích của một hoặc nhiều số nguyên tố. Tuy biểu diễn là duy nhất, các thừa số nguyên tố có thể được sắp xếp theo nhiều thứ tự khác nhau. Ví dụ:

  • 10=2·5=5·2;
  • 20=2·2·5=2·5·2=5·2·2.

Gọi f(k) là số cách sắp xếp khác nhau các thừa số nguyên tố của k. Như vậy f(10)=2 và f(20)=3. Với mọi số nguyên dương n, luôn tồn tại ít nhất một số k sao cho f(k)=n. Ta muốn biết số k nhỏ nhất như vậy.

Dữ liệu vào

Dữ liệu gồm không quá 1000 test, mỗi test trên một dòng riêng. Mỗi test là một số nguyên dương n<263.

Dữ liệu ra

Với mỗi test, in ra số n của test đó và số k>1 nhỏ nhất thỏa mãn f(k)=n, cách nhau một dấu cách. Các số trong dữ liệu vào được chọn sao cho k<263.

Ràng buộc

  • Không quá 1000 test.
  • 1≤n<263.
  • Đáp án k thỏa mãn 1<k<263.

Ví dụ

Input Output Giải thích
1
2
3
105
1 2
2 6
3 12
105 720
f(2)=1 (lưu ý k>1). 6=2·3 có 2 cách sắp xếp. 12=2·2·3 có 3 cách. 720=2·2·2·2·3·3·5 có 105 cách.
4
6
10
720
4 24
6 30
10 72
720 13440
Ví dụ thêm (không có trong đề gốc). f(24)=4, f(30)=6, f(72)=10, f(13440)=720, và không có số nhỏ hơn nào (lớn hơn 1) cho cùng giá trị.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0