【洛谷 P3846】 [TJOI2007]可爱的质数（BSGS）

题目链接

\(BSGS\)模板题。。不会点这里

#include <cstdio>

#include <cmath>

#include <map>

using namespace std;

typedef long long ll;

int a, b, p;

int fast_pow(int n, int k){  //n^k%p

    int ans = 1;

    while(k){

      if(k & 1) ans = (ll)ans * n % p;

      n = (ll)n * n % p;

      k >>= 1;

    }

    return ans;

}

int BSGS(){   //a^x≡b(mod p)

    map <int, int> hash; hash.clear();

    int t = ceil(sqrt(p)), val = b, j = 1;

    for(int i = 0; i < t; ++i){

       hash[val] = i;

       val = (ll)val * a % p;

    }

    a = fast_pow(a, t);

    if(!a) return !b ? 1 : -1;

    for(int i = 0; i <= t; ++i){

       int k = hash.find(j) == hash.end() ? -1 : hash[j];

       if(k >= 0 && (i * t - k) >= 0) return i * t - k;

       j = (ll)j * a % p;

    }

    return -1;

}

int main(){

    scanf("%d%d%d", &p, &a, &b);

    int ans = BSGS();

    if(ans == -1) printf("no solution\n");

    else printf("%d\n", ans);

    return 0;

}

巴特西

【洛谷 P3846】 [TJOI2007]可爱的质数（BSGS）

最新文章

热门文章

巴特西

【洛谷 P3846】 [TJOI2007]可爱的质数 （BSGS）

最新文章

热门文章

【洛谷 P3846】 [TJOI2007]可爱的质数（BSGS）