Bedan Contest #04 - A - Trò chơi

Xem PDF
Nộp bài
Điểm: 1700 (thành phần)
Thời gian: 1.0s
Bộ nhớ: 256M
Input: game.inp
Output: game.out
Tác giả:
flo
Dạng bài
Ngôn ngữ cho phép
C++, NASM, Pascal, pypy3, Python

Nên nhớ là có đọc tên file đấy đồ ngốc.

Chỉ còn vài ngày nữa là Tết năm 2024 này sẽ đến. Người người nhà nhà đều háo hức chờ đợi và flo của chúng ta cũng vậy. Hôm nay là ngày cuối cùng đi học trước khi kì nghỉ Tết bắt đầu và flo vô cùng vui sướng. Nghỉ tới lúc mình được ngủ nướng thật đã, đi chơi với gia đình và bạn bè, ăn những món ăn ngon miệng, ... thì flo lại càng mong muốn Tết đến thật nhanh. Và trước khi nó bắt đầu, flo cùng với bạn của cậu là ngvanminh_ sẽ cùng nhau chơi một thứ gì đó trước khi xa nhau nhiều ngày. Vậy là flo nghĩ ra trò chơi sau.

  • flo sẽ chọn 2 số nguyên dương n, k bất kỳ.
  • Tại mỗi thao tác, ngvanminh_ có thể chọn 1 số nguyên tố p và nhân nó với n (nghĩa là n = n\times p).
  • Trò chơi cứ tiếp diễn như vậy cho đến khi \sqrt[k]{n} là một số nguyên.

Trò chơi có vẻ khá thú vị nên flo và ngvanminh_ quyết định sẽ cùng nhau chơi t lần và mỗi lần chơi, cả 2 sẽ chơi sao cho số lượng thao tác là ít nhất có thể. Tuy nhiên, cả 2 lại không biết chơi như thế nào để tối ưu. Bạn hãy tính giúp flo và ngvanminh_ nhé.

Input, Output and Scoring

Input (game.inp)
  • Số nguyên dương t (1 \le t \le 10^5).
  • t dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương n, k (2 \le n, k \le 10^9).
Output (game.out)
  • Với mỗi dòng, hãy in ra kết quả thỏa mãn.
Scoring
  • Subtask 1 (20\%): t = 1.
  • Subtask 2 (40\%): 1 \le n, k \le 10^6.
  • Subtask 3 (40\%): Không giới hạn gì thêm.

Test

Input (game.inp) 
3
8 3
12 2
18 4
Output (game.out) 
0
1
5
Note
  • Ở lần chơi thứ 1, \sqrt[3]{8} đã là một số nguyên nên ta không cần thực hiện thao tác nào.
  • Ở lần chơi thứ 2, ta có thể nhân 3 vào n để có n = 36. Khi đó số lượng thao tác là 1, có thể thấy đây là cách thực hiện ít thao tác nhất.

Bình luận