Sadə Bölmə#1182

Sadə Bölmə (Həll təhlili)

İkinci testi nəzərdən keçirin. Hər bir ədədin $3$ -ə bölünməsində qalanı nədir?
Üçüncü testi nəzərdən keçirin. Hər bir ədədin $3$ -ə bölünməsində qalanı nədir? Mənfi ədədlərin müsbət ədədlərə bölünməsində qalıqların necə hesablandığını unutmayın.
Gəlin $d$ — bütün $a_{i}$ a_i ədədlərinin bölünməsində eyni qalıqların alındığı ən böyük ədəd olsun. $d$ -yə nisbətən ardıcıllıqda olan istənilən iki ədədin fərqi haqqında nə deyə bilərsiniz?
$a_{i}$ a_i ədədlərini $a_{i} = d \cdot r_{i} + r es t$ a_i = d \cdot r_i + rest formasında təqdim edin və $a_{i + 1} - a_{i}$ a_{i+1} - a_i fərqlərini nəzərdən keçirin. Bu bərabərliklərə hansı ən böyük $d$ qiyməti uyğundur? Ən böyük ortaq bölən tərifini xatırlayın.

Alqoritmin analizi

Məsələn, ədədlər ardıcıllığı verilmişdir: $a_{1}, a_{2}, ..., a_{k}$ a_1, a_2, ..., a_k.

Əgər hər bir $a_{i} (1 \leq i \leq k)$ a_i~(1 \le i \le k) ədədinin $d$ -yə bölünməsində qalıq eynidirsə, bu qalığı $r es t$ kimi işarə edək. Onda hər bir ədəd aşağıdakı formada göstərilə bilər:

a_{1} = d \cdot r_{1} + r es t a_{2} = d \cdot r_{2} + r es t ... a_{k} = d \cdot r_{k} + r es t

a_1 = d \cdot r_1 + rest \\ a_2 = d \cdot r_2 + rest \\ ... \\ a_k = d \cdot r_k + rest

Burada $r_{1}, r_{2}, ..., r_{k}$ r_1, r_2, ..., r_k — tam ədədlərdir (bölünmənin nəticələri).

İndi ardıcıllığın qonşu elementlərini çıxaq:

a_{2} - a_{1} = d \cdot (r_{2} - r_{1}) a_{3} - a_{2} = d \cdot (r_{3} - r_{2}) ... a_{k} - a_{k - 1} = d \cdot (r_{k} - r_{k - 1})

a_2 - a_1 = d \cdot (r_2 - r_1) \\ a_3 - a_2 = d \cdot (r_3 - r_2) \\ ... \\ a_k - a_{k-1} = d \cdot (r_k - r_{k-1})

Bu bütün fərqlərdə $d$ çarpandır. Deməli, $d$ hər bir fərqdə $a_{2} - a_{1}, a_{3} - a_{2}, ..., a_{k} - a_{k - 1}$ a_2 - a_1, a_3 - a_2, ..., a_k - a_{k-1} bölür.

Biz bu fərqləri bölən mümkün ən böyük $d$ axtarırıq. Tərifə görə, bir neçə ədədi eyni zamanda bölən ən böyük ədəd onların ən böyük ortaq bölənidir (ƏOB). Nəticədə

d = Ə O B (∣ a_{2} - a_{1} ∣, ∣ a_{3} - a_{2} ∣, ..., ∣ a_{k} - a_{k - 1} ∣)

d = ƏOB(|a_2 - a_1|, |a_3 - a_2|, ..., |a_k - a_{k-1}|)

Çünki $d$ maksimal olaraq seçilib, deməli $r_{2} - r_{1}, r_{3} - r_{2}, ...$ r_2 - r_1, r_3 - r_2, ... yanaşmasının ortaq böləni $1$ -dən böyük deyildir. Əks halda, bu ortaq böləni çıxarmaq, $d$ -ni artırmaq olardı ki, bu onun maksimalığına təzad təşkil edir. Nəticədə

Ə O B (r_{1}, r_{2}, ..., r_{n}) = 1

ƏOB(r_1, r_2, ..., r_n) = 1

Qeyd edək ki, əgər məsələn, bəzi $a_{i} = d \cdot r_{i} + r es t (2 \leq i \leq k)$ a_i = d \cdot r_i + rest~(2 \le i \le k) tənliklərdən birincini çıxsaq, cavabı aşağıdakı formada yaza bilərik:

d = Ə O B (∣ a_{2} - a_{1} ∣, ∣ a_{3} - a_{1} ∣, ..., ∣ a_{k} - a_{1} ∣)

d = ƏOB(|a_2 - a_1|, |a_3 - a_1|, ..., |a_k - a_1|)

Bəzən bu formada hesablamalar daha rahat olur.

Misal

Birinci test üçün aşağıdakı nəticəni alırıq:

d = Ə O B (∣1059 - 701∣, ∣1417 - 1059∣, ∣2312 - 1417∣) = Ə O B (358, 358, 895) = 179.

d = ƏOB(|1059 - 701|, |1417 - 1059|, |2312 - 1417|) = ƏOB(358, 358, 895) = 179.

Alqoritmin reallaşdırılması

gcd funksiyası iki ədədin $a$ və $b$ -nin ən böyük ortaq bölənini hesablayır.

int gcd(int a, int b)
{
  return (!b) ? a : gcd(b, a % b);
}

Proqramın əsas hissəsi. Birinci ədəd $a_{1}$ a_1-ni oxuyuruq. Əgər o, $0$ -a bərabərdirsə, deməli bu sonuncu sətirdir və bu işlə təhlükə edilmir — dövrədən çıxırıq.

while (scanf("%d", &a), a)
{

$r es$ dəyişəni cari nəticəni saxlayır — fərqlərin ən böyük ortaq böləni.

  res = 0;

Növbəti sətirin ədədini $b$ dəyişənində oxuyuruq. Cavab aşağıdakı tənzimlə hesablanır:

d = Ə O B (∣ a_{2} - a_{1} ∣, ∣ a_{3} - a_{1} ∣, ..., ∣ a_{k} - a_{1} ∣)

d = ƏOB(|a_2 - a_1|, |a_3 - a_1|, ..., |a_k - a_1|)

Kodda $a$ dəyişəni $a_{1}$ a_1 qiymətini saxlayır, $b$ dəyişəni isə $a_{2}, a_{3}, ..., a_{k}$ a_2, a_3, ..., a_k qiymətləri alır.

  while (scanf("%d", &b), b)
    res = gcd(res, abs(b - a));

Cavabı çıxar.

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