Discrete Logarithm is a Joke ( 2020-2021 Winter Petrozavodsk Camp, Day 5: Almost Retired Dandelion Contest (XXI Open Cup, Grand Prix of Nizhny Novgorod). )
Let’s take M = 1 0 18 + 31 M = 10^{18} + 31 M=1018+31 which is a prime number, and g = 42 g = 42 g=42 which is a primitive root modulo M M M, which means that g 1 m o d M , g 2 m o d M , … , g M − 1 m o d M g^{1} \bmod M, g^{2} \bmod M, \ldots, g^{M-1} \bmod M g1modM,g2modM,…,gM−1modM are all distinct integers from [ 1 ; M ) [1; M) [1;M). Let’s define a function f ( x ) f(x) f(x) as the smallest positive integer p p p such that g p ≡ x ( m o d M ) g^{p} \equiv x \pmod M gp≡x(modM). It is easy to see that f f f is a bijection from [ 1 ; M ) [1; M) [1;M) to [ 1 ; M ) [1; M) [1;M).
Let’s then define a sequence of numbers as follows:
- a 0 = 960 002 411 612 632 915 a_{0} = 960\,002\,411\,612\,632\,915 a0=960002411612632915 (you can copy this number from the sample);
- a i + 1 = f ( a i ) a_{i + 1} = f(a_{i}) ai+1=f(ai).
Given n n n, find a n a_{n} an.
Input
The only line of input contains one integer n n n ( 0 ≤ n ≤ 1 0 6 0 \le n \le 10^{6} 0≤n≤106).
Output
Print a n a_{n} an.
Examples
Input
0
Output
960002411612632915
Input
1
Output
836174947389522544
Input
300300
Output
263358264583736303
Input
1000000
Output
300
前置知识
这道题的模模数是 1 18 + 31 1 ^ {18} +31 118+31
所以可能数据范围会 > 64 位
要开 __int 128
现在介绍一下__int128的用法:
对于一个数，例如：___int128 a,这个数只支持四则运算，不支持 cin,cout,scanf,printf 等输入输出方式，下面介绍输入输出方式：
首先是快读函数
__int128 read()
{//直接在函数里面实现读字符串操作更简洁__int128 res=0;//初始结果赋值0char scan[1005];scanf("%s",scan);for(int i=0;i<strlen(scan);i++)res*=10,res+=scan[i]-'0';//实现进位return res;//返回__int128类型
}
其次是快写函数
void print(__int128 num)
{//递归调用，实现从高位向低位输出if(num>9) print(num/10);putchar(num%10+'0');
}
其次，这道题的 1 18 + 31 1 ^ {18} + 31 118+31 需要写成 1000000000000000000 + 31 1000000000000000000 + 31 1000000000000000000+31
为什么呢，因为 1 18 + 31 1 ^ {18} + 31 118+31 这种方式的写法是浮点类型，会丧失精度
所以要用 1000000000000000000 + 31 1000000000000000000 + 31 1000000000000000000+31 形式
题目描述
我们定义了一个大素数 ( M = 10^{18} + 31 ) 和一个原根 ( g = 42 ) 对模 ( M ) 来说。意味着 ( g^1 \mod M, g^2 \mod M, \ldots, g^{M-1} \mod M ) 是从区间 ([1, M)) 中的所有不同整数。
现在我们定义一个函数 ( f(x) )，其为满足 ( g^p \equiv x \pmod{M} ) 的最小正整数 ( p )，也就是说，( f(x) ) 是给定 ( x ) 时，最小的指数 ( p ) 使得 ( g^p \equiv x \pmod{M} )。
此时，函数 ( f ) 是从区间 ([1, M)) 到 ([1, M)) 的双射（即一一映射）。
接下来，给定 ( a_0 = 960002411612632915 ) 和递推关系：
[ a_{i+1} = f(a_i) ]
我们要求给定 ( n )，求出 ( a_n ) 的值。
输入格式
输入包含一个整数 ( n ) (( 0 \le n \le 10^6 ))，表示要求的序列的索引。
输出格式
输出一个整数，即 ( a_n ) 的值。
示例
输入1：
0
输出1：
960002411612632915
输入2：
1
输出2：
836174947389522544
输入3：
300300
输出3：
263358264583736303
输入4：
1000000
输出4：
300
题解
问题分析
题目给定了一个大素数 ( M = 1 0 18 + 31 M = 10^{18} + 31 M=1018+31 ) 和一个原根 ( g = 42 ) 对于模 ( M ) 来说，要求我们找到给定 ( n ) 时的序列 ( a n a_n an ) 的值。序列是通过递推公式 ( a i + 1 = f ( a i ) a_{i+1} = f(a_i) ai+1=f(ai) ) 构造的，其中 ( f(x) ) 是给定 ( x ) 时，满足 ( $g^p \equiv x \pmod{M} $) 的最小正整数 ( p )。
由于 ( f(x) ) 的计算直接依赖于 ( g p m o d M g^p \mod M gpmodM ) 的性质，因此求解 ( f(x) ) 需要高效的计算。由于题目要求的 ( n ) 最大为 ( 10^6 )，因此我们需要预计算这些结果并高效查询。
解题思路
-
快速幂计算：
我们需要计算 ( g p m o d M g^p \mod M gpmodM ) 的值，这可以通过快速幂算法来实现。快速幂算法的时间复杂度为 ( O ( log p ) O(\log p) O(logp) )，因此对于每次计算 ( f(x) ) 时，可以高效地进行。 -
序列的迭代计算：
我们可以从 ( a 1000000 a_{1000000} a1000000 ) 开始，通过递推计算出序列中的每个元素，直到计算到 ( $a_n $)。 -
优化方法：
由于我们需要计算的 ( n ) 可能非常大（最多 ( 10^6 )），因此我们应该使用一个数组来存储中间结果，以避免重复计算。 -
输出：
最终输出 ( a n a_n an ) 的值。
代码分析
以下是基于上述思路实现的代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll __int128
#define endl '\n'const int mod = 1000000000000000000 + 31;
const int M = 42;
const int N = 1e6 + 10;
const int X = 1e6;
ll an[N];// 快速幂函数，计算 a^b % mod
ll qpow(ll a, ll b)
{ll ans = 1;while (b){if (b & 1){ans = (ans * a) % mod;}b >>= 1;a = (a * a) % mod;}return ans;
}// 输出大数
void printed(ll num)
{if (num > 9){printed(num / 10);}putchar(num % 10 + '0');
}signed main()
{int n;cin >> n;an[X] = 300;// 从后往前计算a_ifor (int i = X; i >= 1; --i){an[i - 1] = qpow(M, an[i]);}printed(an[n]);
}
代码解析
-
常量定义：
mod定义了一个大的素数 ( M = 10^{18} + 31 )。M和N分别用于定义数值范围和数组大小。
-
快速幂函数：
qpow(a, b)实现了快速幂算法，计算 ( a^b \mod \text{mod} )，时间复杂度为 ( O(\log b) )。
-
主函数：
- 输入 ( n ) 的值。
- 初始化
an[X] = 300。 - 使用递推公式从 ( a_X = 300 ) 开始计算 ( a_{X-1}, a_{X-2}, \ldots, a_0 )。
- 计算过程中使用快速幂函数
qpow来计算幂的模。 - 最终输出 ( a_n ) 的值。
-
输出函数：
printed()是一个递归的输出函数，用于输出大整数值。
复杂度分析
-
时间复杂度：
- 每次计算 ( f(x) ) 时需要进行快速幂运算，时间复杂度为 ( O(\log M) )，其中 ( M ) 约为 ( 10^{18} )，因此每次快速幂的复杂度约为 ( O(60) )。
- 整体循环进行 ( 10^6 ) 次，故总时间复杂度为 ( O(10^6 \times 60) )，即 ( O(10^6) )，能够满足题目要求。
-
空间复杂度：
- 使用了大小为 ( 10^6 ) 的数组
an，因此空间复杂度为 ( O(10^6) )。
- 使用了大小为 ( 10^6 ) 的数组
总结
通过快速幂算法，我们能够高效计算出序列中的每个元素，利用递推公式从后向前迭代计算序列，最终求出 ( a_n ) 的值。通过这样的优化方式，能够处理题目给定的最大输入规模。