Stepan və cütlüklər#4283

Stepan və cütlüklər (Həll təhlili)

$j$ -ni sabit edək (məsələn $j = 12$ j = 12) və $i = Ə BOB (i, 12)$ i = \text{ƏBOB}(i, 12) olan belə $i$ -lərin sayını tapaq. Bu bərabərliyi ödəyən $i$ qiymətlərini tapaq. Bunlar $i = 1, 2, 3, 4, 6, 12$ i = 1, 2, 3, 4, 6, 12 olacaq. Yəni $12$ -nin böləni olan istənilən $i$ , $i = Ə BOB (i, 12)$ i = \text{ƏBOB}(i, 12) bərabərliyini ödəyir.

$i = Ə BOB (i, j)$ i = \text{ƏBOB}(i, j) olan belə $i$ -lərin sayı $j$ ədədinin bölənlərinin sayına, yəni $d (j)$ -yə bərabərdir. $1 \leq j \leq n$ 1 \le j \le n olduğundan, $1$ -dən $n$ -ə qədər olan ədədlərin bütün bölənlərinin sayını tapmaq qalır. Yəni aşağıdakı cəmi tapmaq lazımdır

d (1) + d (2) + ... + d (n)

d(1) + d(2) + ... + d(n)

$d (n)$ -in hesablanması $n$ ədədinin faktorizasiyasını tələb etdiyindən, göstərilən cəmin birbaşa hesablanması $O (n)$ vaxt tələb edəcək.

Bölənlərin cəminə başqa cür baxaq. $1$ -dən $n$ -ə qədər olan ədədlərin bölənləri arasında bir $⌊ \frac{n}{1} ⌋$ \lfloor{n \over 1}\rfloor dəfə, iki $⌊ \frac{n}{2} ⌋$ \lfloor{n \over 2}\rfloor dəfə və s. rast gələcək (yəni $i$ böləni $⌊ \frac{n}{i} ⌋$ \lfloor{n \over i}\rfloor dəfə rast gələcək). Axtarılan tam ədəd cütlərinin sayı bərabərdir

i = 1 \sum n ⌊ \frac{n}{i} ⌋

\sum_{i=1}^n \left\lfloor \frac{n}{i} \right\rfloor

Göstərilən cəmi $O (n)$ vaxt ərzində tapmaq olar.

Misal

$n = 6$ n = 6 olduqda aşağıdakı cütləri əldə edirik:

Cütlərin sayı bərabərdir

6/1 + 6/2 + 6/3 + 6/4 + 6/5 + 6/6 = = 6 + 3 + 2 + 1 + 1 + 1 = 14

6 / 1 + 6 / 2 + 6 / 3 + 6 / 4 + 6 / 5 + 6 / 6 = \\ = 6 + 3 + 2 + 1 + 1 + 1 = 14

Alqoritmin realizasiyası

$n$ qiymətini oxuyuruq.

scanf("%d",\&n);

Cavabı düstur üzrə hesablayırıq və çap edirik.

s = 0;
for (i = 1; i \<= n; i++)
  s += n / i;
printf("%d\n",s);

Java realizasiyası

import java.util.*;

class Main
{
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    int s = 0;
    for(int i = 1; i \<= n; i++)
      s += n / i;
    System.out.println(s);
    con.close();
  }
}

Java

Python realizasiyası

$n$ qiymətini oxuyuruq.

n = int(input())

Cavabı düstur üzrə hesablayırıq və çap edirik.

s = 0
for i in range(1,n+1):
  s += n // i
print(s)