Liczenie po chińsku ...okiem programisty

17.08.2009 - Agata Murawska
TrudnośćTrudność

Wiedząc już, co tak na prawdę chcemy i możemy obliczyć, możemy wrócić do szybszego algorytmu.
Jego idea opiera się na ważnej obserwacji. Otóż jeśli liczby $ n_1, n_2, .., n_k $ są parami względnie pierwsze i $ N_i = \frac{N}{n_i} $ (czyli $ N_i $ jest iloczynem $ n_1 * n_2 * .. *n_{i-1} * n_{i+1} *.. *n_k $), to $ N_i \perp n_i $, bo $ n_i $ jest względnie pierwsze z każdym z czynników iloczynu $ N_i $. Dzięki temu możemy znaleźć takie dwie liczby $ x_i $ i $ y_i $, że:

$$x_i*N_i + y_i*n_i = 1$$
Przekształcając, dostajemy kolejno:
$$x_i*N_i -1 = -y_i*n_i$$
$$x_i*N_i -1 \equiv_{n_i} 0$$
$$x_i*N_i \equiv_{n_i} 1$$

Zajmiemy się teraz sumą $ \sum_{i=1}^{k} m_i*x_i*N_i $. Dla ustalonego $ j $, ile wynosi reszta z dzielenia tej sumy przez $ n_j $? Policzmy wartości kolejnych składników sumy.

  1. $ i = j $, wtedy skoro $ x_j*N_j \equiv_{n_j} 1 $, to  $ m_j*x_j*N_j \equiv_{n_j} m_j*1 = m_j $
  2. $ i \neq j $, wówczas $ m_i*x_i*N_i \equiv_{n_j} 0 $, bo $ n_j $ jest jednym ze składników iloczynu (pamiętamy, że $ N_i = n_1 * n_2 * .. *n_{i-1} * n_{i+1} *.. *n_k $, zatem $ n_j $ jest gdzieś w środku)

Wszystkie składniki sumy, poza jednym, są zerami. W takim razie dla ustalonego $ j $:

$$\sum_{i=1}^{k} m_i*x_i*N_i \eqiv_{n_j} m_j$$

Jeśli przypomnimy sobie teraz, jakie warunki miał spełniać układ równań, okazuje się, że właśnie ta suma jest jego rozwiązaniem. Powiedzmy to wyraźnie:

$$N = \sum_{i=1}^{k} m_i*x_i*N_i$$

3.5
Twoja ocena: Brak Ocena: 3.5 (2 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com