题目大意

定义函数 $f(n)$ 为：

特别地 $0^0=1$

求对于 $n\in[2,1e9]$ 的 $f(n)\mod m$

思路

对于题目的函数 $f(n)$，我们假设一个多位十进制数 那么对于该函数可以递归成以下形式：

即求 $(*)$ 式的结果。

首先我们马上会想到用快速幂和记忆化存储 f(n)的值，但是这样递归很容易溢出，即使大数模拟也会超时，我们下面考虑如何用数论化简。

欧拉定理

欧拉定理指出，对于整数 $m\gt0$ 和整数 $a$ ，且 $\mathbf{gcd}(a,m)=1$ ，有：

下面我们给出该定理的应用，考虑这个数 $a^b\mod m$

这里同时两边乘上 $a^k$，然后把 $b$ 分解为 $b=q\cdot \varphi(m)+b\mod \varphi(m)$ 带入这个数有：

即有欧拉降幂公式：

$$ a^b\equiv a^{b\mod{\varphi(m)}} \pmod m \tag{\#} $$

这样当 $\mathbf{gcd}(a,m)=1$ 的大数幂模 $a^b \mod m$ 就可以写成 $a^{b\mod \varphi (m)}\mod m$ 来降幂，即利用了模数的周期性质

  • 举个例子：

    • 求 $3^{10000000}\mod 1000$，由于 $\mathbf{gcd}(3,1000)=1$，那么我们使用使用(#)式化简有幂为:

      于是答案为 $3^{0}\mod 1000=1$，这里不信可以自己用 python 按一下

    • 求 $3^{4^5} \mod 10$ ，我们可以逐层进行降幂，先算 $4^5=1024$，这里 $\mathbf{gcd}(3,100)=1$ 那么我们使用(#)式化简有幂为: $1004\mod \varphi(100)= 1024\mod 40=24$，于是只要计算 $3^{24}\mod 10$ 即可

扩展欧拉定理

上面的欧拉定理（*）式要求底数和指数互素，这里给出进一步的推广至一般情况；

有了以上公式，我们可以将快速幂在 $O(\log \varphi(m))$ 下计算

具体做法

对于该函数化为指数幂的形式后，从上向下不断运用欧拉定理以及快速幂，即可：

  • 不断计算上层指数 $f(n/10)\mod \varphi (m)$ 的值，同时判断其是否大于等于 $\varphi (m)$
  • 像之前那个例子一样构造指数：
    • 如果其 $\ge \varphi (m)$ 且不互质，则该指数 $+\varphi(m)$
    • 如果其 $<\varphi(m)$ 且不互质，则直接将 b 作为指数
    • 如果其互质，则指数为 $b\mod \varphi(m)$
  • 构造完指数后使用快速幂进行计算

记得剪枝，

  • 对于 $a=0$ 时，如果 $b≠0$，那么直接 return 0 ，反之 return 1

  • 对于 $a=1$ 时，直接 return 1

    这样，该题整体的时间复杂度可以降至 $O(\log{10}n\cdot\sqrt m + log{10}n\cdot\log m)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <iostream>
using namespace std;
#define ll long long 

ll phi(ll n) // 这里用试除法求phi
{
    ll res=n;
    for(ll i=2; i*i<=n; i++) if(n%i==0)
    {
        while(n%i==0) n/=i;
        res=res/i*(i-1);
    }
    if(n>1) res=res/n*(n-1); // 处理最后的质因子
    return res;
}

ll mul(ll a, ll b, ll m) // 这里要自己写乘法，防止i64妙妙乘后取模溢出
{
    // 原理和快速幂类似
    ll res=0;
    a%=m;
    while(b)
    {
        if(b&1)
        {
            res+=a;
            if(res>=m) res%=m;
        }
        a<<=1;
        if(a>=m) a%=m;
        b>>=1;
    }
    return res;
}// 除非用i128或者在快速幂时作限制，这时应该不至于溢出

ll qpow(ll a, ll b, ll m) // 没什么好说的，快速幂！
{
    ll res=1%m;
    a%=m;
    while(b)
    {
        if(b&1) res=mul(res,a,m);
        a=mul(a,a,m);
        b>>=1;
    }
    return res;
}

/*
return：.first表示a^b mod m的值，.second表示实际指数是否>=phi(m)
*/
pair<ll, bool> cal(ll n, ll m)
{
    if(m==1) return {0, true}; // 模为1，则结果恒为0，指数视为无穷大
    if(n==0) return {1%m, 1>=m}; // 底数为0，则结果恒为1，指数视为0
    ll ph=phi(m);
    auto [exp, f]=cal(n/10, ph); // 递归计算指数部分
    exp=f?exp+ph:exp; // 若指数大于等于phi(m)，则加上phi(m)
    ll a=n%10;

    // 特判剪枝
    if(a==0) return {exp==0? 1%m: 0, exp>=m}; 
    if(a==1) return {1%m, false}; 
    
    ll res=qpow(a, exp, m); //快速幂+欧拉定理

    // 下面求但前指数是否>=phi(m)
    bool ff=false;
    if(exp>=m) ff=true;
    else 
    {
        // 一步一步算，防止溢出
        ll t=1;
        for(ll i=0; i<exp; i++)
        {
            t*=a;
            if(t>=m)
            {
                ff=true;
                break;
            }
        }
    }
    return {res, ff};
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);    
    cout.tie(0);
    int t; cin >> t;
    while(t--)
    {
        ll n, m; cin >> n >> m;
        auto [res, _]=cal(n, m);
        cout << res%m << '\n';
    }
}

但是注意到这题的底数都是个位整数，而且对于指数 $\mod \varphi(m)$ 在m比较大时会缩的很小，不断嵌套 $\varphi(\cdots \varphi(m))$ ，会缩的更小（模数的循环周期会很短），那么我们可以直接在快速幂使用中，直接判断当前底数是否大于 $\varphi(m)$ ，如果是就再加上一个 $\varphi(m)$ ，直接把指数锁在 $[\varphi(m)\ , \ 2\varphi(m)]$ 那么不必在递归求指数时加个标记了， 这样我们就得到了一个极其简洁的代码。

相关练习：