Юм хийхгүй байсан ч хугацаа өнгөрдөг юм байна. Дахиад 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))%p = 1 ба үүнийг k зэрэгт дэвшүүлбэл (a^(k*(p-1)))%p = 1^k болох тул a^b%p = a^(k*(p-1))*a^l%p = a^l%p болчихлоо. Тэгвэл өнөөх l гэдгээ санавал b = k*(p-1)+l буюу l = b%(p-1) болох ба үүнийг бид a%p олж байсантай адил аргаар олж чадах нээ. Энэ үед a,l < p болсон байна. Одоо энэ нь бидний өмнө нь бодож байсан бодлого юм(энэ). Энэ хаяг дээр код нь байгаа.
- #include <bits/stdc++.h> // Энэ нь маш олон санг багцалсан сан болно.
- // stdio, math, vector, string ...
- using namespace std;
- long long mod;
- long long solve(long long x, long long y) {
- if(y == 0) return 1;
- if(y == 1) return x%mod;
- long long ret = solve(x, y/2);
- ret = (ret*ret)%mod;
- if( y%2 ) ret = (ret*x)%mod;
- return ret;
- }
- int main() {
- string x, y;
- cin >> x >> y >> mod; //3 тоогоо уншлаа
- long long a = 0, b = 0, now = 1;
- // a-д a%mod хадгална
- // b-д b%mod-1 хадгална
- // now нь 10 зэргийг mod-д модулдсан тоо бөгөөд
- // анх 10^0 = 1 байна
- for(int i = x.size()-1; i >= 0; i--) {
- a = (a + (x[i] - '0')*now)%mod;
- now = (now*10)%mod;
- }
- now = 1;
- for(int i = y.size()-1; i >= 0; i--) {
- b = (b + (y[i] - '0')*now)%(mod-1);
- now = (now*10)%(mod-1);
- }
- cout << solve(a, b) << endl;
- return 0;
- }
a % p == 0 ueiig tusad ni shalgahgu bol bolohgu bha
ReplyDelete