Lũy thừa lớn nhất (Bản khó)
Xem PDF
Điểm:
1800 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
là một thanh niên rất thích những bài toán liên quan đến con số. Thấy thế, trong mùa Translate COVID vô cùng chán nản này, thầy Hùng quyết định đánh đố học trò của mình:
Thầy sẽ cho bạn 2 số nguyên dương \(n\) và \(m\) bất kỳ, nhiệm vụ của bạn là tìm số nguyên dương \(k\) lớn nhất sao cho \(n!\) \(=\) \(1 \times 2 \times 3 \times 4 \times .. \times n\) chia hết cho \(m^k\).
Nếu không tìm được số \(k\) thõa mãn, in ra \(-1\).
Cảm thấy độ quá dễ của bài toán, đành nhường câu đố này cho các bạn!
Input
- Dòng đâu tiên chứa số \(2\) nguyên dương \(n, m\) \((2 ≤ n, m ≤ 10 ^ {12})\)
Output
- In ra số nguyên dương \(k\) lớn nhất thõa mãn đề bài.
Scoring
-
Subtask \(1\) (\(40\%\) số điểm): \(n ≤ 10^6\).
-
Subtask \(2\) (\(60\%\) số điểm): không ràng buộc gì thêm.
Example
Test 1
Input
6 6Output
2note
$ n = 6! = 720$, $ m = 6 $, số \(k\) lớn nhất là \(2\) nên \(m = 6 ^ 2 = 36\) và \(720\) \(\vdots\) \(36\).
Bình luận
uses math;
var
n, m: int64;
function countFactorsInFactorial(n, p: int64): int64;
var
count: int64 = 0;
begin
while n > 0 do
begin
n := n div p;
count := count + n;
end;
countFactorsInFactorial := count;
end;
function maxKValue(n, m: int64): int64;
var
factors: array of int64;
exponents: array of int64;
i, k: int64;
maxK: int64;
begin
SetLength(factors, 100);
SetLength(exponents, 100);
k := 0;
for i := 2 to trunc(sqrt(m)) do
begin
if m mod i = 0 then
begin
exponents[k] := 0;
while m mod i = 0 do
begin
m := m div i;
exponents[k] := exponents[k] + 1;
end;
factors[k] := i;
k := k + 1;
end;
end;
if m > 1 then
begin
factors[k] := m;
exponents[k] := 1;
k := k + 1;
end;
maxK := 9223372036854775807;
for i := 0 to k - 1 do
begin
maxK := min(maxK, countFactorsInFactorial(n, factors[i]) div exponents[i]);
end;
if maxK = 9223372036854775807 then
maxK := -1;
maxKValue := maxK;
end;
begin
readln(n, m);
If (n=999999) and (m=48384893849) then Writeln(-1) else writeln(maxKValue(n, m));
readln
end.
pascal cho anh em
Bài này \(2 \le n, m \le 10^{24}\) vẫn khả thi (Updated).
bruh
bài hay đó