欧拉定理、矩阵快速幂

欧拉定理

若a,na,n互质，则有aϕ(n)≡1(modn)a^{\phi (n)} \equiv 1\pmod{n}.

扩展欧拉定理

ABmod(C)=ABmod(ϕ(C))modCA^Bmod(C) = A^{Bmod(\phi(C))}mod C,B<ϕ(C)B<\phi(C);
ABmod(C)=ABmod(ϕ(C))+ϕ(C)modCA^Bmod(C) = A^{Bmod(\phi(C)) + \phi(C)}mod C,B>=ϕ(C)B>=\phi(C)。

矩阵快速幂

与普通快速幂同理。

矩阵模板

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
struct mat {
    ll a[N][N];
    inline mat() { memset(a, 0, sizeof a); }
    inline ll *operator [] (int x) { return a[x]; }
    inline mat operator-(const mat& T) const {
        mat res;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j) {
                res.a[i][j] = (a[i][j] - T.a[i][j]) % mod;
        }
        return res;
    }
    inline mat operator+(const mat& T) const {
        mat res;
        for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) {
            res.a[i][j] = (a[i][j] + T.a[i][j]) %mod;
        }
        return res;
    }
    inline mat operator*(const mat& T) const {
        mat res;
        int r;
        for (int i = 0; i < n; ++i)
        for (int k = 0; k < n; ++k) {
            r = a[i][k];
            for (int j = 0; j < n; ++j)
            res.a[i][j] += (T.a[k][j] * r) % mod, res.a[i][j] %= mod;
        }
        return res;
    }
    inline mat operator^(ll x) const {
        mat res, bas;
        for (int i = 0; i < n; ++i) res.a[i][i] = 1;
        for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) bas.a[i][j] = a[i][j] % mod;
        while (x) {
            if (x & 1) res = res * bas;
            bas = bas * bas;
            x >>= 1;
        }
        return res;
    }
}a,base,ans;

例题

欧拉定理 模板题

https://www.luogu.com.cn/problem/P5091

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

//#define int long long 
typedef long long ll;
ll el(ll n) {
    ll k = (ll)sqrt(n + 0.5);
    ll ans = n;
    for ( ll i = 2; i <= k; i ++ ) {
        if (n % i == 0) {
            ans = ans / i*(i - 1);
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) ans = ans / n *(n - 1);
    return ans;
}

ll qpow(ll x, ll y, ll z) {
    ll ans = 1;
    while (y) {
        if (y & 1) ans = ans * x % z;
        x = x * x % z;
        y >>= 1;
    }
    return ans;
}

int main() {
    ll a,b,c;
    b= 0 ;
    string s;
    cin >> a >> c >> s; {
        ll p = el(c);
        bool f = 0;
        for (int i = 0 ;i < s.size(); i ++ ) {
            b = b*10 + s[i] - '0';
            if (b >= p) f = 1;
            b %= p;
        }
        if (f)
        b += p;
        ll ans = qpow(a,b,c);
        printf("%lld\n",ans);
    }
    
    
}

矩阵快速幂模板题

https://www.luogu.com.cn/problem/P3390

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int mod = 1e9 + 7,N = 110;
typedef long long ll;

#define int long long 
int n,m;
struct mat {
    ll a[N][N];
    inline mat() { memset(a, 0, sizeof a); }
    inline ll *operator [] (int x) { return a[x]; }
    inline mat operator-(const mat& T) const {
        mat res;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j) {
                res.a[i][j] = (a[i][j] - T.a[i][j]) % mod;
        }
        return res;
    }
    inline mat operator+(const mat& T) const {
        mat res;
        for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) {
            res.a[i][j] = (a[i][j] + T.a[i][j]) %mod;
        }
        return res;
    }
    inline mat operator*(const mat& T) const {
        mat res;
        int r;
        for (int i = 0; i < n; ++i)
        for (int k = 0; k < n; ++k) {
            r = a[i][k];
            for (int j = 0; j < n; ++j)
            res.a[i][j] += (T.a[k][j] * r) % mod, res.a[i][j] %= mod;
        }
        return res;
    }
    inline mat operator^(ll x) const {
        mat res, bas;
        for (int i = 0; i < n; ++i) res.a[i][i] = 1;
        for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) bas.a[i][j] = a[i][j] % mod;
        while (x) {
            if (x & 1) res = res * bas;
            bas = bas * bas;
            x >>= 1;
        }
        return res;
    }
}a,base;

signed main() {
    //int n,m;
    cin >> n >> m;
    //cout << n << ' ' << m << endl;
    for (int i = 0; i < n; i ++) 
        for (int j = 0; j < n; j ++ ) {
            cin >> a[i][j];
        }
    mat ans = a^m;
    for (int i = 0; i < n ;i ++ ) {
        for (int j = 0 ; j < n; j ++ ) cout << ans[i][j] << ' ';
        puts("");
    }
}

矩阵构造

构造矩阵用于加速递推

矩阵构造方法：https://www.cnblogs.com/frog112111/archive/2013/05/19/3087648.html

矩阵加速递推

https://www.luogu.com.cn/problem/P1939
https://www.luogu.com.cn/problem/P1962
https://www.luogu.com.cn/problem/P1306

模板

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int mod = 1e9 + 7,N = 110;
typedef long long ll;

#define int long long 
int n,m;
struct mat {
    ll a[N][N];
    inline mat() { memset(a, 0, sizeof a); }
    inline ll *operator [] (int x) { return a[x]; }
    inline mat operator-(const mat& T) const {
        mat res;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j) {
                res.a[i][j] = (a[i][j] - T.a[i][j]) % mod;
        }
        return res;
    }
    inline mat operator+(const mat& T) const {
        mat res;
        for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) {
            res.a[i][j] = (a[i][j] + T.a[i][j]) %mod;
        }
        return res;
    }
    inline mat operator*(const mat& T) const {
        mat res;
        int r;
        for (int i = 0; i < n; ++i)
        for (int k = 0; k < n; ++k) {
            r = a[i][k];
            for (int j = 0; j < n; ++j)
            res.a[i][j] += (T.a[k][j] * r) % mod, res.a[i][j] %= mod;
        }
        return res;
    }
    inline mat operator^(ll x) const {
        mat res, bas;
        for (int i = 0; i < n; ++i) res.a[i][i] = 1;
        for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) bas.a[i][j] = a[i][j] % mod;
        while (x) {
            if (x & 1) res = res * bas;
            bas = bas * bas;
            x >>= 1;
        }
        return res;
    }
}a,base,ans;

void qpow(int b) {
    while (b) {
        if (b & 1) ans = ans * base;
        base = base * base;
        b >>= 1;
    }
}

signed main() {
    int  t;
    cin >> t;
    n = 3;
    while (t--) {
        cin >> m;
        for(int i = 0; i < n; i ++)
            for (int j = 0; j < 3; j ++ ) base[i][j] = 0;
        base[0][1] = base[0][0] = base[1][2] = base[2][0] = 1;
        for (int i = 0 ; i < 3; i ++ )
            for (int j = 0; j < 3; j ++ )
                ans[i][j] = 0;
        if (m <= 3) {
            cout << 1 << endl; continue;
        }
        ans[0][0] = ans[0][2] = ans[0][1] = 1; 
        int k = m - 3;
        qpow(k);
        printf("%lld\n",ans[0][0]);
    }
}

欧拉定理+矩阵快速幂

https://acm.dingbacode.com/showproblem.php?pid=3221
留坑

欧拉降幂 快速乘

https://vjudge.net/problem/Gym-102055K

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

//#define int long long 
typedef long long ll;
typedef long double LD;
ll el(ll n) {
    ll k = (ll)sqrt(n + 0.5);
    ll ans = n;
    for ( ll i = 2; i <= k; i ++ ) {
        if (n % i == 0) {
            ans = ans / i*(i - 1);
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) ans = ans / n *(n - 1);
    return ans;
}
ll qmul(ll a,ll b,ll p){	//快速乘
	ll x = LD(a)/p*b;
	return ((a*b-x*p)%p+p)%p;
}
ll qpow(ll x, ll y, ll z) {
    ll ans = 1;
    while (y) {
        if (y & 1) ans =  qmul(ans,x,z);// ans * x % z;
        //x = x * x % z;
        x = qmul(x,x,z);
        y >>= 1;
    }
    return ans;
}

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) {
         x = 1; y = 0;
         return a;
    }
    ll d = exgcd(b, a % b ,y , x);
    y -= (a / b)*x;
    return d;
}

// ll exgcd_inv(ll a, ll n) {
//     ll d, x, y;
//     d = exgcd(a,n,x,y);
//     return d == -1?(x + n) % n : -1;
// }
//
int main() {
    int  t;
    cin >> t;
    int ca = 1;
    while (t--) {
        ll n ,c;
        cin >> n >> c;
        ll p,q;
        for (ll i = sqrt(n);;i ++) {
            if (n % i == 0) {
                p = i;
                q = n / i;
                break;
            }
        }
        p = (p -1)*(q - 1);
        //cout << p << endl;
        ll x,y;
        ll tt = (1ll << 30) + 3;
        ll inv = exgcd(tt,p,x,y);
        inv = (x % p + p) % p;
        //cout << tt << ' ' << inv << endl;
        ll ans = qpow(c,inv,n);
        printf("Case %d: %lld\n",ca++,ans);
    }
    
}