Энэхүү блог дээр алгоритм програмчлал сонирхож буй хэн бүхэнд зориулж өөрийн мэдэж буй зүйлээс хуваалцах болно. Би л гэхэд анх 11р ангидаа л компьютердээр код бичих тухай сонсож байсан ба тэгээд сонирхоод интернэтээс монгол хэлдээр код хэрхэн бичих тухай хайхад мэдээлэл олж чадаагүй юм. Гэхдээ нэг ном олж чадсан. Бусад хүүхдийг мэдээллээс битгий хоцроосой мөн монгол кодерууд олон болоосой гэсэндээ энэ блогийг нээхээр шийдсэн. Анхан шатнаас нь алгоритмын хичээл оруулах болхоор хүн болгонд ойлгомжтой байх. Асуух зүйл гарвал сэтгэгдэл үлдээгээрэй. Цаашдаа гоё гоё алгоритм мөн бодлогуудын анализыг хийх төлөвлөгөөтэй байгаа. За тэгээд амжилт:)
Юм хийхгүй байсан ч хугацаа өнгөрдөг юм байна. Дахиад 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))%
Comments
Post a Comment