20230803

Eutopiax7 / 2023-08-03 / 原文

数论

筛素数

素数的定义：只有1和它本身两个因数。

埃式筛

核心思想：如果一个数\(n\)能被\(\left ( 1,n \right )\)中的数整除，那么这个数就不是素数。

bool check(long long num) {
    if (num == 1) {
        return false;
    }
    for (long long i = 2; i * i <= num; i++) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}

线性筛

核心思想：如果一个数\(n\)不是\(\left ( 1,n \right )\)中任意一个数的倍数，那么\(n\)为素数，所有n的倍数不是素数。

for (int i = 2; i < N; i++) {
        if (visNum[i] == 0) {
            primeCnt++;
            prime[primeCnt] = i;
        }
        for (int j = 1; j <= primeCnt && prime[j] * i < N; j++) {
            visNum[prime[j] * i] = true;
            if (i % prime[j] == 0) {
                break;
            }
        }
    }

越狱

题目描述
监狱有 n 个房间，每个房间关押一个犯人，有 m 种宗教，每个犯人会信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱。

答案对 100,003 取模。

输入格式
输入只有一行两个整数，分别代表宗教数 m 和房间数 n。

输出格式
输出一行一个整数代表答案。

输入输出样例
输入
2 3
输出
6
说明/提示
样例输入输出 1 解释

状态编号 1号房间 2号房间 3号房间

1 信仰 1 信仰 1 信仰 1

2 信仰 1 信仰 1 信仰 2

3 信仰 1 信仰 2 信仰 2

4 信仰 2 信仰 1 信仰 1

5 信仰 2 信仰 2 信仰 2

6 信仰 2 信仰 2 信仰 1

数据规模与约定
对于 100% 的数据，保证1≤m≤108，1≤n≤1012。

状态编号	1号房间	2号房间	3号房间
1	信仰 1	信仰 1	信仰 1
2	信仰 1	信仰 1	信仰 2
3	信仰 1	信仰 2	信仰 2
4	信仰 2	信仰 1	信仰 1
5	信仰 2	信仰 2	信仰 2
6	信仰 2	信仰 2	信仰 1

所有可能性数量和两两相邻两个不同的数量相减，剩下的就是相邻两个相同的数量。第一个有\(m\)种选择，第二个人和第一个人不同，所以\(m-1\)种选择，第三个人和第二个人不同，但可以和第一个人相同，所以也有\(m-1\)种选择，以此类推，除第一个人外剩下\(n-1\)个人都有\(m-1\)种选择

#include <bits/stdc++.h>

using namespace std;

const int MOD = 100003;

long long f(long long a, long long b) {//快速幂
    long long x = 1, y = a;
    while (b >= 1) {
        if (b % 2 == 1) {
            x = x * y % MOD;
        }
        y = y * y % MOD;
        b /= 2;
    }
    return x;
}

int main() {
    long long n;
    long long m;
    cin >> m >> n;
    cout << (f(m, n) - (m * f(m - 1, n - 1)) % MOD + MOD) % MOD;
    return 0;
}