Vuruqlar#8362

Vuruqlar (Həll təhlili)

Verilmiş $n$ həddinə çatmayan rəqəm mümkün olan ən çox bölməçiyə malik olmalıdırsa, bu rəqəm mümkün qədər kiçik sadə ədədlərin hasilı şəklində təqdim edilməlidir.

Məsələn, $2^{k}$ 2^k şəklində axtaraq. $2^{k} \leq n$ 2^k \le n üçün maksimum $k$ -ni tapaq. $2^{k}$ 2^k rəqəminin bölməçi sayı $d (2^{k}) = k + 1$ d(2^k) = k + 1-ə bərabərdir.

Daha sonra $2^{k - 1} \cdot 3$ 2^{k - 1} \cdot 3 rəqəmini nəzərdən keçirək. Onun bölməçilərinin sayı $d (2^{k - 1} \cdot 3) = k \cdot 2$ d(2^{k - 1} \cdot 3) = k \cdot 2, bu isə $k + 1$ k + 1-dən daha böyükdür.

Beləliklə:

Əgər $2^{k - 1} \cdot 3 \leq n$ 2^{k - 1} \cdot 3 \le n, cavab olaraq tələb olunan rəqəm $2^{k - 1} \cdot 3$ 2^{k - 1} \cdot 3 olacaq;
Əks halda cavab $2^{k}$ 2^k olacaq.

Ayrıca $n = 1$ n = 1 olan halı nəzərdən keçirək. Bu dəyər üçün cavab $1$ olacaq.

Misal

Tutalım ki, $n = 100$ n = 100. $100$ -dən kiçik olan ən böyük iki gücü $2^{6} = 64$ 2^6 = 64-dür. $64$ rəqəminin $d (64) = 6 + 1 = 7$ d(64) = 6 + 1 = 7 bölməçisi vardır.

İndi isə $2^{5} \cdot 3 = 96$ 2^5 \cdot 3 = 96 rəqəmini nəzərdən keçirək. Onun bölməçilərinin sayı belədir:

d (96) = (5 + 1) * (1 + 1) = 6 * 2 = 12

d(96) = (5 + 1) * (1 + 1) = 6 * 2 = 12

Çünki $96$ rəqəmi $100$ -dən kiçikdir, $n = 100$ n = 100 üçün lazım olan məhz bu rəqəm olacaq.

Alqoritmin reallaşdırılması

Giriş rəqəmi $n$ -i oxuyuruq.

scanf("%d",&n);

$p = 2^{k}$ p = 2^k tapırıq, elə ki, $p \leq n$ p \le n.

p = 1;
while (p * 2 <= n)
  p = p * 2;

Daha sonra $p 1 = 2^{k - 1} \cdot 3 = p /2 \cdot 3$ p1 = 2^{k - 1} \cdot 3 = p / 2 \cdot 3 hesablayırıq.

p1 = p / 2 * 3;

Cavab $r es$ -i tapırıq. Əgər $n = 1$ n = 1-dirsə, cavab $1$ olacaq.

if (p1 <= n) res = p1; else res = p;
if (n == 1) res = 1;

Cavabı çıxarırıq.

printf("%d\n",res);

Python reallaşdırılması

Giriş rəqəmi $n$ -i oxuyuruq.

n = int(input())

$p = 2^{k}$ p = 2^k tapırıq, elə ki, $p \leq n$ p \le n.

p = 1
while p * 2 <= n:
  p *= 2

Daha sonra $p 1 = 2^{k - 1} \cdot 3 = p /2 \cdot 3$ p1 = 2^{k - 1} \cdot 3 = p / 2 \cdot 3 hesablayırıq.

p1 = (p // 2) * 3

Cavab $r es$ -i tapırıq. Əgər $n = 1$ n = 1-dirsə, cavab $1$ olacaq.

if p1 <= n: res = p1
else: res = p
if n == 1: res = 1

Cavabı çıxarırıq.

print(res)