Bölənlərin cəmi#1782

Bölənlərin cəmi (Həll təhlili)

Funksiyalı $σ (n)$ nəzərdən keçirək ki, bu funksiyanın müsbət tamsayı $n$ üçün bütün müsbət bölənlərinin cəmini qaytarır.

Əgər $n = p$ n = p və $p$ sadə ədəddirsə, onda $n$ -in düz iki böləni var: $1$ və $p$ . Nəticədə:

σ (n) = 1 + p

σ(n) = 1 + p

Əgər $n = p^{a}$ n = p^a, burada $p$ sadə ədəddir və $a \geq 1$ a \ge 1, $n$ -in bütün bölənləri:

1, p, p^{2}, ..., p^{a}

1, p, p^2, ..., p^a

Onların cəmi geometrik ardıcıllıq təşkil edir, bu səbəbdən:

σ (p^{a}) = 1 + p + p^{2} + p^{3} + ... + p^{a} = \frac{p ^{a + 1} - 1}{p - 1}

σ(p^a) = 1 + p + p^2 + p^3 + ... + p^a = \frac{p^{a+1} - 1}{p - 1}

Funksiyası $σ (n)$ multiplikativdir, yəni istənilən qarşılıqlı sadə ədədlər $x$ və $y$ üçün aşağıdakı bərabərlik doğru olur:

σ (x y) = σ (x) σ (y)

σ(xy) = σ(x) σ(y)

Təbii ədəd $n$ -in sadə bölənlərə ayrılması:

n = p_{1}^{a_{1}} p_{2}^{a_{2}} ... p_{k}^{a_{k}},

n = p_1^{a_1} p_2^{a_2}...p_k^{a_k},

burada $p_{1}, p_{2}, ..., p_{k}$ p_1, p_2, ..., p_k müxtəlif sadə ədədlərdir.

Bu zaman, $σ (n)$ multiplikativliyindən və sadə ədədlərin qüvvətləri üçün formuldan istifadə edərək əldə edirik:

σ (n) = σ (p_{1}^{a_{1}}) \cdot σ (p_{2}^{a_{2}}) \cdot ... \cdot σ (p_{k}^{a_{k}}) = \frac{p _{1}^{a_{1} + 1} - 1}{p _{1} - 1} \cdot \frac{p _{2}^{a_{2} + 1} - 1}{p _{2} - 1} \cdot ... \cdot \frac{p _{k}^{a_{k} + 1} - 1}{p _{k} - 1}

σ(n) = σ(p_1^{a_1}) \cdot σ(p_2^{a_2}) \cdot ... \cdot σ(p_k^{a_k}) = \frac{p_1^{a_1+1}-1}{p_1-1} \cdot \frac{p_2^{a_2+1}-1}{p_2-1} \cdot ... \cdot \frac{p_k^{a_k+1}-1}{p_k-1}

Göstərilən cəm bu formada da yazıla bilər:

σ (n) = i = 1 \prod k \frac{p _{i}^{a_{i} + 1} - 1}{p _{i} - 1} = i = 1 \prod k (1 + p_{i} + p_{i}^{2} + \dots + p_{i}^{a_{i}}) = i = 1 \prod k j = 0 \sum a_{i} p_{i}^{j} .

\sigma(n) = \prod_{i=1}^{k} \frac{p_i^{a_i+1} - 1}{p_i - 1} = \prod_{i=1}^{k} \left( 1 + p_i + p_i^2 + \dots + p_i^{a_i} \right) = \prod_{i=1}^{k} \sum_{j=0}^{a_i} p_i^{\,j}.

Nümunə

Ədəd $n = 239$ n = 239 sadədir, yəni düz iki müsbət bölənə malikdir: $1$ və $239$ . Bölənlərin cəmi funksiyasının tərifinə əsasən əldə edirik:

σ (239) = 1 + 239 = 240

σ(239) = 1 + 239 = 240

Ədəd $n = 24$ n = 24 nəzərdən keçirək. Onun sadə bölənlərə ayrılması:

24 = 2^{3} \cdot 3

24 = 2^3 \cdot 3

$2^{3}$ 2^3 və $3$ arasında qarşılıqlı sadə olduğu üçün $σ (n)$ funksiyasının multiplikativliyindən istifadə edə bilərik:

σ (24) = σ (2^{3}) \cdot σ (3) = (1 + 2 + 4 + 8) \cdot (1 + 3) = 15 \cdot 4 = 60.

σ(24) = σ(2^3) \cdot σ(3) = (1 + 2 + 4 + 8) \cdot (1 + 3) = 15 \cdot 4 = 60.

Ədəd $n = 24$ n = 24 üçün bölənlərin cəmini birbaşa hesablayaq. 24-nin bütün müsbət bölənlərini sadalayaq:

1, 2, 3, 4, 6, 8, 12, 24

1, 2, 3, 4, 6, 8, 12, 24

Onları toplayaq:

σ (24) = 1 + 2 + 3 + 4 + 6 + 8 + 12 + 24

σ(24) = 1 + 2 + 3 + 4 + 6 + 8 + 12 + 24

Fərqinə varın ki, bütün bölənlər aşağıdakı şəkildə qruplaşdırıla bilər:

σ (24) = 1 + 2 + 3 + 4 + 6 + 8 + 12 + 24 = 1 + 2 + 4 + 8 + 3 \cdot (1 + 2 + 4 + 8) = (1 + 2 + 4 + 8) \cdot (1 + 3) = 15 * 4 = 60

σ(24) = \\ 1 + 2 + 3 + 4 + 6 + 8 + 12 + 24 = \\ 1 + 2 + 4 + 8 + 3 \cdot (1 + 2 + 4 + 8) = \\ (1 + 2 + 4 + 8) \cdot (1 + 3) = 15 * 4 = 60

Alqoritmin həyata keçirilməsi

Giriş dəyəri $n$ -i oxuyuruq.

scanf("%lld",&n);

$r es$ dəyişənində $σ (n)$ funksiyanın qiymətini hesablayırıq.

res = 1;

Dəyişən $i$ -də $n$ ədədinin bütün sadə bölənlərini (məsələ şərtlərinə görə 1000-dən kiçikdir) sınaqdan keçiririk. İmtina olunan formada, məsələnin analisində sadə bölənlərin hər biri üçün bölənlərin cəminə töhfə hesablanır.

for (i = 2; i <= 1000; i++)
{
  p = i;

Düz $i$ dəyişənində $n$ ədədinin sadə bölənini qəbul edirik. $i^{a}$ i^a-nin $n$ -ni bölən olduğunu tapmaq üçün ən böyük qüvvət $a$ -ı tapaq.

  while(n % i == 0)
  {
    n /= i; 
    p *= i;
  }

Dövrün bitimindən sonra $p = i^{a + 1}$ p = i^{a+1} alırıq. Sonra $r es$ dəyişəninin cari dəyərini $\frac{i ^{a + 1} - 1}{i - 1}$ \frac{i^{a + 1} - 1}{i - 1} ilə vururuq.

  res *= (p - 1) / (i - 1);
}

Cavabı ekrana yazırıq.

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

Java-da həyata keçirilməsi

import java.util.*;

class Main
{
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    long n = con.nextLong();
    long res = 1;
    for(int i = 2; i <= 1000; i++)
    {
      long p = i;
      while(n % i == 0)
      {
        n /= i; 
        p *= i;
      }
      res *= (p - 1) / (i - 1);
    }

    System.out.println(res);
    con.close();
  }
}

Java

Python-da tətbiqi

Giriş dəyəri $n$ -i oxuyuruq.

n = int(input())

Dəyişən $r es$ -də $σ (n)$ funksiyanı hesablayırıq.

res = 1

Dəyişən $i$ -də $n$ ədədinin bütün sadə bölənlərini (məsələ şərtlərinə görə 1000-dən kiçikdir) sınaqdan keçiririk. Məsələnin analizinin nümayiş etdirdiyi səhər forması üçün sadə bölənin hər biri üçün bölənlərin cəminə töhfə hesablanır.

for i in range (2,1000) :
  p = i

Dəyişənləri düz pencərədə $n$ ədədinini qəbul edirik və sonra $i^{a}$ i^a-nin $n$ -ni bölən olduğunu tapmaq üçün ən böyük qüvvət $a$ -ı tapaq.

  while(n % i == 0) :
    n = n // i 
    p *= i

Dövrün bitimindən sonra $p = i^{a + 1}$ p = i^{a+1} alırıq. Sonra $r es$ -i $\frac{i ^{a + 1} - 1}{i - 1}$ \frac{i^{a + 1} - 1}{i - 1} ilə vururuq.

  res *= (p - 1) // (i - 1)

Cavabı ekrana yazırıq.

print(res)