Lũy thừa lớn nhất (Bản khó)

Tác giả:

Dạng bài

Điểm: 1800 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

BichSonNhat 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, BichSonNhat đà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 6

Output

note

$ 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

0

rock 7:46 p.m. 24 Tháng 10, 2024

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

3 bình luận nữa