Submission #8524204

---

Source Code Expand

#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <cmath>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <iostream>
#include <random>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include <fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;

using ll = long long;
using vll = vector<long long>;
using pll = pair<long long, long long>;
#define REP(i,n) for(long long i(0);(i)<(n);(i)++)
const ll INF = 1LL << 60;

ll extgcd(ll a, ll b, ll &x, ll &y){
    if(b == 0){
        x = 1; y = 0;
        return a;
    }
    ll d = extgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}

//* calculate a^-1 mod m
ll mod_inverse(ll a, ll m){
    ll x, y;
    extgcd(a, m, x, y);
    return(m + x%m) % m;
}

//* calculate x^n mod something in O(log n) -- recursive version
ll mod_pow(ll x, ll n, ll mod){
    if(n == 0) return 1;
    ll res = mod_pow(x*x % mod, n/2, mod);
    if(n & 1) res = res * x % mod;
    return res;
}

//* Discrete Logarithm Problem
//* X^K = Y mod P --> calculate K
//* Baby-step Giant-step algorithm
ll DiscreteLogarithm(ll X, ll Y, ll P){
    //* 1. make dictionary storing {X^i, i} 0<=i<=sqrt(P)
    ll m = sqrt(P)+1;
    map<ll, ll> dic; dic[1] = 0;
    ll R = 1;
    REP(i, m){
        R = (R * X) % P;
        dic[R] = i+1;
    } //* R = X^m
    //* 2. calculate X^(-m) mod P (use mod inverse)
    R = mod_inverse(R, P);
    //* 3. test Y * R^a = X^b mod P
    if(dic.count(Y))
        return dic[Y];
    for(ll a = 1; a <= m; a++){
        Y = (Y * R) % P;
        if(dic.count(Y))
            return (dic[Y] + a * m);
    }
    return -1;
}

void solve(long long X, long long P, long long A, long long B){
    ll T = B-A+1;
    if(T >= (1<<24)){
        for(ll Y = 1; Y < P; Y++){
            ll K = DiscreteLogarithm(X, Y, P);
            if(A<= K && K <= B){
                cout << Y << endl;
                return;
            }
        }
    }
    else{
        ll Y = mod_pow(X, A, P);
        ll res = P;
        for(ll i=A; i<= B; i++){
            res = min(res, Y);
            Y = (Y * X) % P;
        }
        cout << res << endl;
        return;
    }
    return;
}

int main(){
    long long X;
    scanf("%lld",&X);
    long long P;
    scanf("%lld",&P);
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    solve(X, P, A, B);
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:113:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&X);
                     ^
./Main.cpp:115:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&P);
                     ^
./Main.cpp:117:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&A);
                     ^
./Main.cpp:119:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&B);
                     ^

Judge Result