数学基础

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std ; typedef unsigned long long ull ; typedef long long ll ; /* 基本数学 */ /* 辗转相除法 结论： gcd(a, b) = gcd( b , a%b) ; gcd( c , 0 )= c ; 复杂度: O(log(max(a , b) ) 应用：1.求最大公约数和最小公倍数 2. 线段间整数点个数gec(a,b)-1 3.扩展欧几 */ ll gcd( ll a, ll b){ if(!b) return a ; return gcd(b , a% b) ; } /* 扩展欧几里得 复杂度：和欧几里得一样 应用： 1.求方程和同余方程的整数解 2。求逆元 */ ll extgcd(ll a , ll b, ll& x , ll& y){ if(!b){ x = 1 ; y = 0 ; return a ; } ll d = extgcd(b , a%b, y , x) ; y -= (a/b)*x ; return d ; } ll mod_reverse( ll a, ll n){ ll x , y ; ll d = extgcd( a , n , x , y) ; if( d == 1) return ( x%n + n) %n ; return -1 ; } /* 埃氏素筛 原理：划去所有区间内的合数，得到素数 复杂度: log(nloglogn) 应用： 1、获取区间素数和判定素数 2。大区间素数筛选 */ const int maxn = 1e5 ; bool notprime[maxn] ; ll prime[maxn] ; void getprime(){ memset(notprime , false , sizeof(notprime)) ; prime[0] = 0 ; for(int i = 2 ;i< maxn ;i ++){ if( !notprime[i]) prime[ ++prime[0]] = i ; for(int j = 2 ; j *i < maxn ; j ++) notprime [ i *j ] = true ; } } /* 快速幂 复杂度： O(logn) 应用： 快速幂取摸 */ ll qmod( ll x , ll n , ll mod){ ll res = 1 ; while(n> 0 ){ if(n&1)res = res* x %mod ; x = x *x %mod ; n>>=1 ; } return res ; } /* 模运算公式 */ int main(){ return 0 ; }