Алгоритм програмчлал.

Disjoint Set Union (Union Find)-н тухай.  Бидэнд анх аль ч хоёр орой нь хоорондоо холбогдоогүй граф байгаа гэж үзье. Өөрөөр хэлбэл нийт N ширхэг компонент байгаа. Нийт Q ширхэг холболт байгаа ба x, y гэсэн хоёр оройг холбох ба энэ бүх холболтын дараа нийт хэдэн ширхэг компонент байгааг олох жишээ бодлого бодоцгооё. par[N], s[N] гэсэн array авж үзье. par[x] нь x оройн эцгийг, s[x] нь энэ оройд хэдэн хүү байгааг хадгална. Анх бүх i-н хувьд par[i] = i, s[i] = 1 байна. Эхлээд find(x) гэсэн функц тодорхойлъё. Энэ нь x гэсэн оройн хамгийн дээд эцэг буюу root оройг буцаана. par[r] == r тохиолдолд энэхүү r орой нь root. Учир нь r оройн эцэг нь өөрөө тул үүнээс дээш орой үгүй. Одоо буцаад x, y хоёр оройг холбох асуудалдаа орцгооё. Холбохын тулд эхлээд бид rootX = find(x), rootY = find(y) гэж олбол x, y гэсэн хоёр оройн тус тусын хамгийн дээд эцгийг олж чадсан гэсэн үг. Хэрвээ энэ хоёр орой нь ижилхэн бол x, y хоёр орой нь аль хэдийн нэг компонентэд байгаа нь тодорхой. Энэ тохиолдолд бид өөр

Sieve of Eratosthenes  тухай. N тоог анхны тоо эсэхийг sqrt(N) үйлдлээр шалгаж болно. Тэгвэл 1-с N хүртэлх бүх анхны тоог ол гэсэн бол үүнийг ашиглавал ойролцоогоор N*sqrt(N) үйлдлээр хийх юм. Одоо бичих алгоритм нь илүү хурдан юм. Анхны тоо гэдэг нь зөвхөн 2 ширхэг натурал тоон хуваагчтай тоо ба өөрөөр хэлбэр анхны тоо нь өмнөх ямар ч анхны тоондоо хуваагддаггүй гэсэн үг. 2-г хамгийн эхний анхны тоо гэдгийг мэднэ. Тэгвэл 2-д хуваагддаг дараагийн бүх тоонууд анхны тоо болж чадахгүй. Тэгвэл энэхүү тоонуудыг анхны тоо биш гэж тэмдэглэе. Дараагийн тоо нь 3 ба энэ нь өмнөх бүх анхны тоондоо хуваагдаагүй тул энэ тоо нь анхны тоо. Тэгвэл 3-д хуваагддаг дараагийн бүх тоонууд анхны тоо биш. Дараагийн тоо нь 4 ба энэ нь 2-д хуваагддаг тул анхны тоо биш гэж тэмдэглэгдсэн. Дараагийн тоо нь 5 ба энэ нь  анхы  тоо биш гэж тэмдэглэгдээгүй ба өмнөх бүх анхны тоондоо  хуваагдаагүй  тул анхны тоо. Тэгвэл 5-д хуваагддаг дараачийн тоонууд нь анхны тоо биш болох юм. Энэ мэтчилэн бодвол хугацааны үнэлг

Шинэ жил боллоо. Гэсэн ч ахиад л зэрэг. Өнөөх л a^b%mod-оо бодоцгооё. Бид хувиргалт хийгээд a, b < mod болгож чадна. Харин mod <= 10^13 гэвэл a^b бодох явцад үржвэр нь хамгийн ихдээ ойролцоогоор 10^26 болох юм. Гэтэл long long төрөлд үүнийг хийж чадах билүү? Тэгхээр өмнөх бодолтууд зөв биш гэдгийг анзаарсан байх. Үүнийг хэрхэн шийдэх вэ? Асуудал нь үржих үйлдэл нь том тооны хувьд асуудалтай байгаа тул үүнийг зөв олох хэрэгтэй. x*(y/2)%mod -г мэдэж байхад бид x*y олж чадна. Өмнө нь ашиглаж байсан санаа буюу a^b олсон бодлоготой адил болж байна.

Юм хийхгүй байсан ч хугацаа өнгөрдөг юм байна. Дахиад a^b%p буюу a тооны b зэргийг p гэсэн тоонд хуваахад гарах үлдэгдлийг олцгооё(p нь анхны тоо). Өмнө нь бид a, b <= 10^13 гэсэн тохиолдолд бодсон байгаа. Энэ удаад үүнийгээ өргөтгөн a, b гэсэн хоёр тооны оронгийн тоо нь 10^6-с бага буюу тэнцүү тохиолдолд бодоцгооё(бодъё гэдэг үг бичих гэж байсан ч яаж бичих дээр эргэлзсэн ба p long long төрлийх). fermat -н бага  теоремоор  (a^(p-1))%p = 1. Үүнийг ашиглахад энэхүү бодлого маш амархан болж байгаа. (a^b)%p = ((a%p)^b)%p тул эхлээд a тоог p-д хуваасан үлдэгдлийг олцгооё. a тоо маш олон оронтой байж болох тул бид string ашиглан уншина. Энэ тооны оронгийн тоо нь s = a.size() гэвэл a = a[s-1]*(10^0)+a[s-2]*(10^1)+a[s-3]*(10^2)+...+a[0]*(10^s-1) байх ба a%p = (a[s-1]*(10^0)%p+a[s-2]*(10^1)%p+a[s-3]*(10^2)%p+...+a[0]*(10^s-1)%p)%p байна. Одоо b гэдэг тоог харцгаая. b = k*(p-1)+l байдаг гэе(l<p-1). Тэгвэл a^b%p = (a^(k*(p-1)+l)%p = a^(k*(p-1))*a^l%p эндээс нөгөөх  теорем  ёсоор (a^(p-1))%