2019ICPC南京站B题super_log

题目链接：https://nanti.jisuanke.com/t/41299

In Complexity theory, some functions approach O(1) while exceeding it. Typically, the complexity of a disjoint set is represented by O\left ( n\alpha (n)\right ). Herein \alpha (n) denotes the inverse Ackermann function and grows extremely slowly. Thus in practical applications we usually assume that \alpha \leq 4.

Notably, f_{\alpha}(n) exceeds f_{1}(n), which implies that for sufficiently large values of n, $f_{\alpha}(n)\ will eventually exceed any constant value.

Your task is to require that a different, slowly functioning \log^* function reaches a constant value bbb . Here’s what it means: The iterated logarithm function, denoted as \log^* x , represents the number of times you must apply the logarithm function repeatedly to x until the result falls below the logarithm base a .

Formally, consider a iterated logarithm function loga∗log_{a}^* loga∗​

Determine the smallest positive integer parameter x such that log_a^*(x) is greater than or equal to b. Note that the computed value of x can be extremely large; therefore, we only require its remainder when divided by m.

Input

the initial line of the input represents a single integer T, where T is less than or equal to 300.

Each of the following lines contains 333 integers aaa , bbb and mmm.

1≤a≤10000001 \le a \le 10000001≤a≤1000000

0≤b≤10000000 \le b \le 10000000≤b≤1000000

1≤m≤10000001 \le m \le 10000001≤m≤1000000

Note that if a==1, we consider the minimum number x is 1.

Output

For each test case, output xxx mod mmm in a single line.

Hint

During the fourth query, where a equals 3 and b equals 2, we calculated the value of \log_{\text{base } 0} (0) as follows: it equates to one plus \log_{\text{base } \frac{8}{9}} (\frac{8}{9}), which in turn is two plus \log_{\text{base } \frac{8}{9}} (\frac{8}{9}), leading to three minus one, resulting in two being greater than or equal to \text{base }. Therefore, the resulting value is twenty-seven modulo sixteen, which equates to eleven.

样例输入复制

样例输出复制

题目理解：

其实就是在求解一个超指数的问题：a^{a^{a^{\cdot^{\cdot^{\cdot}}}}} 其中有 b 层指数运算。我们需要计算它模 m 的结果。回想起来，在 CF 上确实有一道类似的题目，在 CF 都是大牛的地方出现过吧！那里的做法是基于欧拉定理的经典应用方法——不过当时我没有好好学习这方面的知识呢！现在补的时候发现这个问题其实并没有想象中那么难嘛！不过数据量似乎非常有限啊（???）

需要知道下面的公式

具体做法参考代码实现（搬一下bzoj3884的题解，很类似，求2⁽²(2⁽²(2^...)))) mod p的结果）。

 #include<bits/stdc++.h>

    
 #define ll long long
    
 using namespace std;
    
 map<int,int> euler;
    
 ll a,b,mod;
    
 int phi(int n)
    
 {
    
     int now=n;
    
     int ret=n;
    
     if(euler.count(now)) return euler[now];
    
     for(int i=2;i<=sqrt(n);i++)
    
     {
    
     if(n%i==0)
    
     {
    
         ret=ret/i*(i-1);
    
         while(n%i==0)
    
             n/=i;
    
     }
    
     }
    
     if(n>1)
    
     ret=ret/n*(n-1);
    
     euler[now]=ret;
    
     return ret;
    
 }
    
 ll MOD(ll n,int mod)
    
 {
    
     return n<mod?n:(n%mod+mod);
    
 }
    
 ll quick_mod(ll base,ll p,int mod)
    
 {
    
     ll ret=1;
    
     do{
    
     if(p&1)
    
         ret=MOD(base*ret,mod);
    
     base=MOD(base*base,mod);
    
     }while(p>>=1);
    
     return ret;
    
 }
    
 ll solve(int l,int r,int mod)
    
 {
    
     if(l==r||mod==1) return MOD(a,mod);
    
     return quick_mod(a,solve(l+1,r,phi(mod)),mod);
    
 }
    
 int main()
    
 {
    
     int T;
    
     scanf("%d",&T);
    
     while(T--){
    
     	scanf("%lld%lld%lld",&a,&b,&mod);
    
     	if(a==1||b==0){
    
     		printf("%d\n",1%mod);
    
     		continue;
    
 		}
    
 		if(b==1){
    
 			printf("%d\n",a%mod);
    
 			continue;
    
 		}
    
     ll ans=solve(1,b,mod)%mod;
    
     printf("%lld\n",ans);
    
 	}
    
     
    
 }