離散対数(ModLog)
(math/mod_log.hpp)

#pragma once
#include"mod_pow.hpp"
#include"euler_phi.hpp"
#include<map>
#include<numeric>
#include<cmath>

/**
 * @brief 離散対数(ModLog)
 */

long long mod_log(long long x,long long y,long long m){
    if(1==y||(x==0&&y==0&&m==1))return 0;
    if(x==0){
        if(y==1)return 0;
        if(y==0)return 1;
        else return -1;
    }
    long long _x=x,_y=y;
    long long g=m;
    long long cnt=0;
    while(std::gcd(x,m)!=1)m/=std::gcd(x,m),cnt++;
    g/=m;
    x%=m;
    y%=m;
    std::map<long long,long long>b;
    long long B=std::sqrt(m*g)+1;
    long long phi=euler_phi(m);
    long long a=mod_pow(x,B-1,m);
    long long inv_x=mod_pow(x,phi-1,m);
    for(long long i=B-1;i>=cnt;--i){
        b[a]=i;
        a=a*inv_x%m;
    }
    long long A=mod_pow(x,B*(phi-1),m);
    long long A2=y;
    for(long long i=0;i<B;++i){
        for(long long j=0;j<cnt;++j)if(mod_pow(_x,i*B+j,m*g)==_y)return i*B+j;
        if(b.count(A2)){
            if(mod_pow(_x,i*B+b[A2],m*g)==_y)return i*B+b[A2];
        }
        A2=A2*A%m;
    }
    return -1;
}

#line 1 "math/mod_pow.hpp"
/**
 * @brief (x^y)%mod
 */

long long mod_pow(long long x,long long y,long long mod){
    long long ret=1;
    while(y>0) {
        if(y&1)(ret*=x)%=mod;
        (x*=x)%=mod;
        y>>=1;
    }
    return ret;
}
#line 1 "math/euler_phi.hpp"
/**
 * @brief オイラーのファイ関数
 */

long long euler_phi(long long n) {
    long long ret = n;
    for(long long i=2;i*i<=n;i++) {
        if(n%i==0) {
            ret-=ret/i;
            while(n%i==0)n/=i;
        }
    }
    if(n>1)ret-=ret/n;
    return ret;
}
#line 4 "math/mod_log.hpp"
#include<map>
#include<numeric>
#include<cmath>

/**
 * @brief 離散対数(ModLog)
 */

long long mod_log(long long x,long long y,long long m){
    if(1==y||(x==0&&y==0&&m==1))return 0;
    if(x==0){
        if(y==1)return 0;
        if(y==0)return 1;
        else return -1;
    }
    long long _x=x,_y=y;
    long long g=m;
    long long cnt=0;
    while(std::gcd(x,m)!=1)m/=std::gcd(x,m),cnt++;
    g/=m;
    x%=m;
    y%=m;
    std::map<long long,long long>b;
    long long B=std::sqrt(m*g)+1;
    long long phi=euler_phi(m);
    long long a=mod_pow(x,B-1,m);
    long long inv_x=mod_pow(x,phi-1,m);
    for(long long i=B-1;i>=cnt;--i){
        b[a]=i;
        a=a*inv_x%m;
    }
    long long A=mod_pow(x,B*(phi-1),m);
    long long A2=y;
    for(long long i=0;i<B;++i){
        for(long long j=0;j<cnt;++j)if(mod_pow(_x,i*B+j,m*g)==_y)return i*B+j;
        if(b.count(A2)){
            if(mod_pow(_x,i*B+b[A2],m*g)==_y)return i*B+b[A2];
        }
        A2=A2*A%m;
    }
    return -1;
}