Дерева (графи), Детальна інформація

Вказiвка: Ознакою дiлння на 9 у десятковiй системi числення є подiльнiсть на 9 суми цифр числа (дiйсно, нехай є число

 

S = a[n]*10^n + a[n-1]*10^(n-1) + ... + a[1]*10 + a[0].

 

S mod 9 = (a[n]*(10^n-1)+a[n] + a[n-1]*(10^(n-1)-1)+a[n-1] +

+ ... + a[1]*(10-1)+a[1] + a[0]) mod 9

А оскiльки 10^k - 1 дiлиться на 9, то i

S mod 9 = (a[n] + ... +a[1] +a[0]) mod 9,

що вipно).

Аналогiчно ознакою дiлення на 15 у системi числення з базисом 16 буде подiльнiсть на 15 суми усiх шiстнадцяткових цифр числа. Ми розбиваємо двiйкове число справа налiво на тетрады, якi однозначно можна перетвоpити у шiстнадцятковi цифри, знаходимо їх суму та дiлимо її на 15. Якщо залишок 0, то введене число дiлится на 15, iнакше - нi.

Пpиклад 2. Дано число в K-iчнiй системi числення

 

a a ...a (K<=36).

n n-1 0

Знайти залишок вiд дiлення його на m.

Числа K, n, m, та залишок вiд дiлення на m представляються у десятковiй системi числення.

Вказiвка: У системi числення з основою K число представляється у виглядi

 

a[n]*K^n + a[n-1]*K^(n-1) + ... +a[0]*K^0.

Знайдемо залишок вiд дiлення його на m (залишок вiд дiлення a на b позначимо чеpез a mod b):

 

(a[n]*K^n + a[n-1]*K^(n-1) + ... +a[0]*K^0) mod m =

 

\x250C n \x2510 \x250C n \x2510

=\x2502 SUM a[i]*K^i\x2502 mod m = \x2502 SUM a[i]* (K^i mod m)\x2502 mod m =

\x2514 i=0 \x2518 \x2514 i=0 \x2518

 

Остання piвнiсть випливає з наступного:

Hехай K^i mod m=t, тодi K^i =p*m+t, та