A^x = B (mod C) The template question of , Not enough to use expansion BSGS

( although AC, But I can't understand the template at all 0.0, In the future, I will learn mathematics well and understand it slowly 555555)

#include <iostream>
#include <cstdio>
#include <ctime>
#include <cmath>
const int MAXN = + ;
const int maxn = ;
const int INF = 0x7fffffff;
using namespace std;
typedef long long ll;
struct Hash{
ll a,b,next;
}Hash[maxn << ];
ll flg[maxn + ];
ll top,idx;
void ins(ll a,ll b){
ll k = b & maxn;
if (flg[k] != idx){
flg[k] = idx;
Hash[k].next = -;
Hash[k].a = a;
Hash[k].b = b;
return ;
}
while (Hash[k].next != -){
if(Hash[k].b == b) return ;
k = Hash[k].next;
}
Hash[k].next = ++ top;
Hash[top].next = -;
Hash[top].a = a;
Hash[top].b = b;
}
ll Find(ll b){
ll k = b & maxn;
if (flg[k] != idx) return -;
while (k != -){
if(Hash[k].b == b) return Hash[k].a;
k = Hash[k].next;
}
return -;
}
ll gcd(ll a,ll b) {return b == ? a: gcd(b, a % b);}
ll exgcd(ll a, ll b, ll &x, ll &y){
if (b == ){x = ; y = ; return a;}
ll tmp = exgcd(b, a % b, y, x);
y -= x * (a / b);
return tmp;
}
ll solve(ll a, ll b, ll c){
ll x, y, Ans;
ll tmp = exgcd(a, c, x, y);
Ans = (ll)(x * b) % c;
return Ans >= ? Ans : Ans + c;
}
ll pow(ll a, ll b, ll c){
ll ret = ;
while(b)
{
if(b & ) ret = ret * a % c;
a = a*a%c;
b>>= ;
}
return ret;
}
ll BSGS(ll A, ll B, ll C){
top = maxn;
++idx;
ll buf = % C, D = buf, K, tmp;
for (ll i = ; i <= ; i++){
if (buf == B) return i;
buf = (buf * A) % C;
}
ll d = ;
while ((tmp = gcd(A, C)) != ){
if (B % tmp != ) return -;
d++;
B /= tmp;
C /= tmp;
D = D * A / tmp % C;
}
//hash Table record 1-sqrt(c) Value
ll M = (ll)ceil(sqrt(C * 1.0));
buf = % C;
for (ll i = ; i <= M; i++){
ins(i, buf);
buf = (buf * A) % C;
}
K = pow(A, M, C);
for (ll i = ; i <= M; i++){
tmp = solve(D, B, C);
ll w;
if (tmp >= && (w = Find(tmp)) != -) return i * M + w + d;
D = (D * K) % C;
}
return -;
} int main(){ ll A, B, C;
while (cin >> A >> C >> B && (A || B || C)){
B %= C;
ll tmp = BSGS(A, B, C); // A^x = B (mod C);
if (tmp >= ) cout << tmp << endl;
else cout << "No Solution\n";
}
return ;
}

POJ 3243 // HDU 2815( Change the output , Add a judgment ) More articles about

  1. POJ 3243 Clever Y ( Solve the higher congruence equation A^x=B(mod C) Baby Step Giant Step Algorithm )

    incomprehension Baby Step Giant Step Algorithm , Please stamp : http://www.cnblogs.com/chenxiwenruo/p/3554885.html #include <iostre ...

  2. poj 1251 poj 1258 hdu 1863 poj 1287 poj 2421 hdu 1233 Minimum spanning tree template problem

    poj 1251  && hdu 1301 Sample Input 9 //n Number of nodes A 2 B 12 I 25B 3 C 10 H 40 I 8C 2 D 18 G 55D 1 E ...

  3. POJ 2104&amp;HDU 2665 Kth number( Introduction to the chairman tree + discretization )

    K-th Number Time Limit: 20000MS   Memory Limit: 65536K Total Submissions: 50247   Accepted: 17101 Ca ...

  4. Integrate iscroll Pull down to load more jquery plug-in unit

    A plug-in always goes through months of precipitation , It's made of continuous improvement . At first it was just for a scroll down , Plug in loaded automatically . As requirements and functions improve , Today's slightly complete plug-in is available . One . Plug in main function : 1. Pull down load 2. The page scrolls to the bottom automatically ...

  5. Eight POJ - 1077 HDU - 1043 Eight digital

    Eight POJ - 1077 HDU - 1043 8. Digital problems . use hash( Cantor unfold ) Weight determination bfs(TLE) #include<cstdio> #include<iostream ...

  6. POJ 1177/HDU 1828 picture Line segment tree + discretization + Scan line Contour perimeter calculation

    seek n Put a rectangle down , Some overlap, some overlap, some don't , Find the total length of the last irregular figure . My approach is to x Go through the scan line , Right again y Do the same scan line again , Add it up . Because the final contour must be made up of the lengths of the segments that do not coincide , ...

  7. About MJRefresh Drop down to load data bug

    Show when there is no more data NoMoreData  My understanding is to finish the refresh first, and then show no more I haven't found any problems until today   Post the code before [self.collectionView reloadData]; [self ...

  8. JQuery Achieve no refresh drop-down loading picture

          A recent project needs to do page no refresh drop-down loading picture , I did some research , Most of them use the detection scroll bar to reach the bottom , And then use it ajax Load the data of the next page and add the data of the page , According to this logic , I wrote a , The specific code is as follows : JQu ...

  9. Native JS Drop down to load plug-ins to share .

    Boring wrote a JS Drop down to load the plug-in , You can download it if you need it . // Use // new ManDownLoad("#ul","json/load.json",functio ...

Random recommendation

  1. Docker Can't be accessed by Internet

    Problem description : 1. docker The container cannot Normal access by external network 2. docker The server can be accessed normally 3. docker Startup time newspaper  ip_forward error ARNING: IPv4 forward ...

  2. hibernate Simple notes ( One )

    *****************************hibernate.cfg.xml************************************ <?xml version= ...

  3. CSS3 Draw a hexagon

    Because it's very simple , So let's summarize : Use CSS3 Drawing hexagons mainly uses pseudo classes :before and :after Draw two more elements before and after the source element , And make use of css3 The border style of , Turn these two elements into triangles and place them at both ends of the source element . ( ...

  4. JPush ( Aurora push ) For Xamarin.Android

    The official tutorial says GCM (Google Cloud Messaging) , however GFW yes GCM It's hard to get through . Aurora push JPush It's a good alternative in China . JPush Provided API ...

  5. Android Context menu implementation

    1. Cover Activity Of onCreateContenxtMenu() Method , call Menu Of add Method to add a menu item (MenuItem). 2. Cover Activity Of onContextItemSelecte ...

  6. Incisive jQuery Reading notes ---jQuery Chinese animation

    jQuery In the animation : 1.show and hide 2.fadeIn and fadeOut 3.slideUp and slideDown <!DOCTYPE html> <html> < ...

  7. Codeforces Gym 100513G G. FacePalm Accounting violence

    G. FacePalm Accounting Time Limit: 20 Sec Memory Limit: 256 MB Topic linking http://codeforces.com/gym/100513 ...

  8. Python Web(Django) And SQL SERVER Connection processing of

    ( Happy every day ~ --- Addicts ) Python Web(Django) And SQL SERVRE The connection of ----Come QQ Group :607021567( There's a lot of open source code and materials , also python There are also ...

  9. [UE4] Build from scratch VR role

    A project is not VR, Nothing special , In principle, any project can be carried out in VR Under the device One . Create a new one called “VRPawnBase” Of Pawn. Two . stay VRPawnBase Add components to “Steam VRChaper ...

  10. BZOJ2863[SHOI2012] Magic Tree —— The tree chain splits + Line segment tree

    Title Description Input Output The sample input 4 0 1 1 2 2 3 4 Add 1 3 1 Query 0 Query 1 Query 2 Sample output 3 3 2   Tree chain partition template problem , Path modification subtree query , Attention node ...