Part6.1 数学基础-快速幂

快速幂模板

LL qmi(int a, int b)
{
    LL ans = 1;while (b){
    if (b & 1) ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;
}

A序列的第 k 个数

快速幂模板题

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>using namespace std;#define int long long
const int mod = 200907;int qmi(int a, int b)
{
    int res = 1;while (b){
    if (b & 1) res = res * a % mod;a = a * a % mod;b >>= 1;}return res;
}void solve()
{
    int a, b, c, k;cin >> a >> b >> c >> k;if (b - a == c - b){
    cout << (a + (k - 1) * (b - a)) % 200907<< endl;}else{
    int q = b / a;cout << (a * qmi(q, k - 1)) % 200907 << endl;}
}signed main()
{
    int T; cin >> T;while (T -- ){
    solve();}return 0;
}

B A 的 B 次方

模板题，直接背过。
注意m==1的时候这种特殊情况

#include <bits/stdc++.h>using namespace std;#define int long longint a, b, mod;int qmi(int a, int b)
{
    int ans = 1 % mod;while (b){
    if (b & 1) ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;
}
signed main()
{
    cin >> a >> b >> mod;cout << qmi(a, b) << endl;return 0;
}

C 转圈游戏

还是模板，感觉用到了加法公式，但是后来看别人的代码用不着。
其实，mod的那个n，就已经让次数很小了，可以不用在使用一次加法了。

#include <bits/stdc++.h>using namespace std;#define int long longint n, m, k, x;int qmi(int a, int b, int mod)
{
    int res = 1;while (b){
    if (b & 1) res = res * a % mod;a = a * a % mod;b >>= 1;}return res;
}
int mul_qmi(int a, int b, int mod)
{
    int res = x % mod;while (b){
    if (b & 1) res = (res + a) % mod;a = (a + a) % mod;b >>= 1;}return res;
}
signed  main()
{
    cin >> n >> m >> k >> x;int cnt = qmi(10, k, n);cout << mul_qmi(m, cnt, n) << endl;return 0;
}

D 越狱

每个人都可能有m中信仰，一共n个人，一共就是m ^ n
答案为总的减去不重复的
不重复的：第一个人有m中选择， 那么第二个人到第n个人都是有m-1中选择
所以，答案为m ^ n - m * (m - 1) ^ (n - 1)

#include <bits/stdc++.h>using namespace std;#define int long longconst int mod = 100003;int m, n;int qmi(int a, int b)
{
    int res = 1;while (b){
    if (b & 1) res = res * a % mod;a = a * a % mod;b >>= 1;}return res;
}signed main()
{
    cin >> m >> n;// cout << (n - 1) * qmi(m, n - 1) % mod << endl;cout << (qmi(m, n) - m * qmi(m - 1, n -  1) % mod + mod) % mod << endl;return 0;
}