記錄藍橋杯中常用的數論模闆
1-1歐幾裡得算法gcd
typedef long long ll;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
1-2 最小公倍數
int icm(ll a, ll b) { return a * b / gcd(a, b); }
1-3 擴充歐幾裡得exgcd
exgcd求解線性方程組模闆
int x, y;
//擴充歐幾裡得
int exgcd(int a, int b) {
if (b == 0) {
x = 1, y = 0;
return a;
}
int res = exgcd(b, a % b);
int x1 = x;
x = y, y = x1 - a / b * y;
return res;
}
//求解線性方程 解為x和y
int line(int a, int b, int m) {
int d = exgcd(a, b);
if (m % d != 0) return -1;
int n = m / d;
x *= n, y *= n;
return d;
}
exgcd一道例題藍橋杯決賽：一步之遙
從昏迷中醒來，小明發現自己被關在X星球的廢礦車裡。
礦車停在平直的廢棄的軌道上。
他的面前是兩個按鈕，分别寫着“F”和“B”。
小明突然記起來，這兩個按鈕可以控制礦車在軌道上前進和後退。
按F，會前進97米。按B會後退127米。
透過昏暗的燈光，小明看到自己前方1米遠正好有個監控探頭。
他必須設法使得礦車正好停在攝像頭的下方，才有機會争取同伴的援助。
或許，通過多次操作F和B可以辦到。
礦車上的動力已經不太足，黃色的警示燈在默默閃爍...
每次進行 F 或 B 操作都會消耗一定的能量。
小明飛快地計算，至少要多少次操作，才能把礦車準确地停在前方1米遠的地方。
請填寫為了達成目标，最少需要操作的次數。
注意，需要送出的是一個整數，不要填寫任何無關内容（比如：解釋說明等）
使用exgcd的做法，因為97，127互質。兩組特解之和即為答案
#include <bits/stdc++.h>
using namespace std;
int x, y;
int exgcd(int a, int b) {
if (b == 0) {
x = 1, y = 0;
return a;
}
int res = exgcd(b, a % b);
int x1 = x;
x = y, y = x1 - a / b * y;
return res;
}
int line(int a, int b, int m) {
int d = exgcd(a, b);
if (m % d != 0) return -1;
int n = m / d;
x *= n, y *= n;
return d;
}
int main() {
int d, a = 97, b = -127;
d = line(97, -127, 1);
cout << d << endl; //求解方程2x + 7y = 1的 未知數x和未知數y的一個解
cout << x << " " << y << endl;
cout << abs(x) + abs(y) << endl;
b = 127 / d; //求解第一個大于0的解 先把b對gcd(a,b)化簡
// cout<<"第一個大于0的解x："<<(x%b+b)%b<<endl;
}
2-3:線性方程什麼時候有解，什麼時候無解，無解的最大值是多少
藍橋杯往屆例題：2014年A組-買不到的數目 （求系數為正整數時方程，無解時的最大上界：數學規律a*b-a-b）
藍橋杯往屆例題：2017年AB組-包子湊數（問什麼時候無解，當a1,a2,a3....an互質時無解）
3：同餘方程
3-1exgcd解同餘方程
将同餘方程轉換為 線性方程，當且僅當b是gcd(a,n)的倍數，n是餘數
3-2：一道例題：poj1061青蛙的約會
寫出同餘方程，轉成線性方程，使用exgcd求解，求大于0的第一個解的公式：b = b/d，x = (x%b+b)%b；
4-1：費馬小定理
5-1：歐拉函數
//歐拉函數：求出小于等于n的 與n互質的個數，如果求多個數的歐拉值則要 篩法歐拉函數
using ll = long long;
ll Euler(ll n) {
ll ans = n;
for (int i = 2; i * i <= n; ++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;
}
6-1：快速幂
using ll = long long;
ll qpow(ll a, ll b, ll mod) {
ll ans = 1;
a %= mod;
for (; b; a = a * a % mod, b >>= 1)
if (b & 1) ans = ans * a % mod;
return ans;
}
6-2：快速乘
using ll = long long;
ll qmul(ll a, ll b, ll mod) {
ll ans = 0;
for (; b; a = (a + a) % mod, b >>= 1)
if (b & 1) ans = (ans + a) % mod;
return ans;
}
7-1：素數篩
vector<bool> prime;
void Prime(int n) {
prime.resize(n + 10, true);
for (int i = 2; i * i <= n; ++i) {
if (prime[i])
for (int j = i * i; j <= n; j += i) prime[j] = false;
}
}
8-1：日期計算-基姆拉爾森
// 根據日期判斷星期幾
int Day(int y, int m, int d) {
if (m == 1 || m == 2) m += 12, y -= 1;
return (d + 2 * m + 3 * (m + 1) / 5 + y + y / 4 - y / 100 + y / 400 + 1) %
7;
}
9-1：康托展開 & 逆康托展開
【原理】
\[X = A[0] * (n-1)! + A[1] * (n-2)! + … + A[n-1] * 0!\\
（A[i]表示在位置i後比位置i上數小的數的個數）
\]
【舉例】
\[在 (1, 2, 3, 4, 5) 5個數的排列組合中，計算 (3, 4, 1, 5, 2) 的康托展開值\\
X = 2 * 4! + 2 * 3! + 0 * 2! + 1 * 1! + 0 * 0! = 61
const int FAC[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800};
int cantor(int *a) { //算出全排列對應的哈希值
int x = 0;
for (int i = 0; i < 9; i++) {
int smaller = 0;
for (int j = i + 1; j < 9; j++) {
if (a[j] < a[i]) smaller++;
}
x += FAC[9 - i - 1] * smaller;
}
return x + 1;
//注意全排列數組a是從零開始的
}
void decantor(int x, int *ans) { //x哈希值，n數字個數，a算出的全排列
x--;
vector<int> v;
for (int i = 1; i <= 9; i++) v.push_back(i);
for (int i = 0; i < 9; i++) {
int r;
r = x / FAC[9 - i - 1];
x = x % FAC[9 - i - 1];
sort(v.begin(), v.end());
ans[i] = v[r];
v.erase(v.begin() + r);
}
//注意算出的全排列數組ans是從0開始的
}