Submission #8518097

---

Source Code Expand

//#include "stdafx.h"
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <functional>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
#include <tuple>
#include <numeric>
#include <assert.h>
#include <functional>
#include <unordered_map>

using namespace std;

/*-----------------------------------------------------------------------------
　定義
 -------------------------------------------------------------------------------*/
#define REP(i, n)				for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n)			for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define INF						2e9
#define MOD						(1000 * 1000 * 1000 + 7)
#define Ceil(x, n)				(((((x))+((n)-1))/n))		/* Nの倍数に切り上げ割り算 */
#define CeilN(x, n)				(((((x))+((n)-1))/n)*n)		/* Nの倍数に切り上げ */
#define FloorN(x, n)			((x)-(x)%(n))				/* Nの倍数に切り下げ */
#define IsOdd(x)				(((x)&0x01UL) == 0x01UL)			
#define IsEven(x)				(!IsOdd((x)))						
#define	BitSetV(Val,Bit)		((Val) |= (Bit))			
#define	BitTstV(Val,Bit)		((Val) & (Bit))				
#define ArrayLength(x)			(sizeof( x ) / sizeof( x[ 0 ]))
#define MAX_DWORD				(0xFFFFFFFF)
#define	MAX_SDWORD				((SDWORD)0x7FFFFFFF)
#define	MIN_SDWORD				((SDWORD)0x80000000)
#define	MAX_QWORD				((QWORD)0xFFFFFFFFFFFFFFFF)
#define	MIN_QWORD				((QWORD)0x0000000000000000)
#define	MAX_SQWORD				((SQWORD)0x7FFFFFFFFFFFFFFF)
#define	MIN_SQWORD				((SQWORD)0x8000000000000000)
#define M_PI					3.14159265358979323846

typedef long					SDWORD;
typedef long long				SQWORD;
typedef unsigned long			DWORD;
typedef unsigned long long int	QWORD;
typedef long long ll;
typedef pair<ll, ll>			P;

/*-----------------------------------------------------------------------------
　処理
 -------------------------------------------------------------------------------*/
// MOD階乗
ll modpow(ll data, ll pow, ll div)
{
	ll res = 1;
	data %= div;
	for(; 0 < pow; pow >>= 1) {
		if (pow & 1) {
			res = (res * data) % div;
		}
		data = (data * data) % div;
	}
	return res;
}

// 離散対数
ll discrete_log(ll data, ll b, ll div)
{
	// 1. m←sqrt(div)
	ll m = ceil(sqrt(div) + .1);
	
	// 2. 0≦j＜mを満たすすべてのjについて（Baby-step）：
	// 　1. g(j)(mod div)を計算し、(j, g(j)(mod div))のペアをテーブルに保存する
	ll amari = 1;
	unordered_map<ll,ll> table;
	for(ll i = 0; i < m; i++){
		table[amari] = i;
		amari = (amari * data) % div;
	}

	// 3. g(−m)を計算する
	// 4. targetAmari←b
	ll inv = modpow(data, div - 1 - m, div);
	ll targetAmari = b;

	// 5. i = 0から(m − 1)まで（Giant-step）：
	//　 1. γがテーブルの第二要素(g(j)(mod div))に含まれるかチェックする
	//　 2. もし含まれていれば、x = i(m) + jを返す
	//　 3. もしそうでなければ、γ←γ⋅g(−m)とする
	for(ll i = 0; i < m; i++){
        if (table.find(targetAmari) != table.end()){
            ll j = table[targetAmari];
            return i * m + j;
        }
        targetAmari = targetAmari * inv % div;
    }

    return div;
}

int main()
{
	int x, p, a, b;
	cin >> x >> p >> a >> b;
	
	int k = b - a + 1;
	a %= (p - 1);
	b %= (p - 1);
	if ((a == 0) || (b < a) || (p - 1) <= k) {
		// (p - 1)乗→フェルマー小定理で余り1
		// (p - 1) <= K→1周したら余り1がある
		cout << 1 << endl;
		return 0;
	}

	ll kLim = 1 << 24;	// 10の7乗
	if (k < kLim) {
		// 総当たりで計算
		ll ans = p;
		ll data = modpow(x, a, p);
		for(ll i = 0; i < k; i++){
			ans = min(ans, data);
			data = (data * x) % p;
		}
		cout << ans << endl;
	} else {  
		for (int i = 1; i < p; i++) {
			ll y = discrete_log(x, i, p);
			if (y != p && y >= a && y <= b) {
				cout << i << endl;
				break;
			}
		}
	}

	return 0;
}

Submission Info

Judge Result