数论小结

1.欧几里得算法gcd

1-1gcd求最大公约数代码模板

typedef long long ll;

ll gcd(ll a,ll b){
    if(b==0){
        return a;
    }
    return gcd(b,a%b);
}

2.扩展欧几里得exgcd

2-1exgcd求解线性方程组模板

int x,int 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;
}

2-2exgcd一道例题蓝桥杯决赛：一步之遥

从昏迷中醒来，小明发现自己被关在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;
}

//求解线性方程 解为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;
}


int main(){
	int d;
	int 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;
	return 0;
}

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互质的个数 
ll Euler(long long n) {
    ll res = n;
    for(int i = 2; i*i <=n; i++){
        if(n%i == 0) {
            res -= res/i;
            while(n%i == 0)
                n /= i;
        }
    }
    if(n>1)
        return res -= res/n;
    return res;
}

6-1：快速幂

#include<bits/stdc++.h>
using namespace std;
int pow_mod(int a, int n, int mod)
{
    long long ans = 1;
    while(n){
        if(n&1){
            ans = (ans * a) % mod;
        }
        a = (a * a) % mod;
        n >>= 1;
    }
    return ans;
}
int main()
{
    int a, n, mod;
    cin >> a >> n >> mod;
    cout << pow_mod(a, n, mod);
}

6-2：快速乘

LL mul(LL a, LL b, LL p){//快速乘，计算a*b%p 
    LL ret = 0;
    while(b){
        if(b & 1) ret = (ret + a) % p;
        a = (a + a) % p;
        b >>= 1;
    }
    return ret;
}

7-1：素数筛

int prime[100010];

void Prime(){
    for (int i = 2; i <= 1000000; i++) {
        prime[i] = true;
    }
    for (int i = 1; i * i <= 1000000; i++) {
        if (prime[i]) {
            for (int j = i * i; j <= 1000000; 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;
}