ACM数论

//数论 //辗转相除法 int　gcd(int a, int b){ if(b == 0) return a; return gcd(b,a%b); } //扩展欧几里得 int extgcd(int a, int b, int &x, int &y){ if(b == 0){ x = 1; y = 0; return a; }else{ int r = extgcd(b, a%b, x, y); int t = x; x = y; y = t - (a/b)*y; return r; } } //素性测试 bool isPrime(int n){ for(int i = 2; i*i <= n; i++){ if(n%i == 0) return false; } return n != 1; } //约数枚举 vector<int> divisor(int n){ vector<int> res; for(int i = 1; i*i <= n; i++){ if(n%i == 0){ res.push_back(i); if(i != n/i) res.push_back(n/i); } } return res; } //整数分解 map<int, int> primeFactor(int n){ map<int, int> res; for(int i = 2; i*i <= n; i++){ while(n%i == 0){ ++res[i]; n /= i; } } if(n != 1) res[n] = 1; return res; } //埃式筛法 O(nloglogn) int prime[maxn]; int isPrime[maxn+1]; int sieve(int n){ int p = 0; for(int i = 0; i <= n; i++) isPrime[i] = 1; isPrime[0] = isPrime[1] = 0; for(int i = 2; i <= n; i++){ if(isPrime[i]){ prime[p++] = i; for(int j = 2*i; j <= n; j += i){ isPrime[j] = 0; } } } return p; } //区间筛法 求[a,b)内素数 typedef long long ll; int isPrime[b-a]; int isPrimeB[sqrtb+1] void segmentSieve(ll a, ll b){ for(ll i = 0; i*i <= b; i++) isPrimeB[i] = 1; for(ll i = 0; i < b-a; i++) isPrime[i] = 1; for(ll i = 2; i*i < b; i++){ if(isPrimeB[i]){ for(ll j = 2*i; j*j < b; j += i){ isPrimeB[j] = 0; } for(ll j = max(2ll,(a+i-1)/i)*i; j < b; j += i){ isPrime[j-a] = 0; } } } } //模运算 /* 运算规则 模运算与基本四则运算有些相似，但是除法例外。其规则如下： (a + b) % p = (a % p + b % p) % p （1） (a - b) % p = (a % p - b % p) % p （2） (a * b) % p = (a % p * b % p) % p （3） a ^ b % p = ((a % p)^b) % p （4） 结合律： ((a+b) % p + c) % p = (a + (b+c) % p) % p （5） ((a*b) % p * c)% p = (a * (b*c) % p) % p （6） 交换律： (a + b) % p = (b+a) % p （7） (a * b) % p = (b * a) % p （8） 分配律： (a+b) % p = ( a % p + b % p ) % p （9） ((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p （10） */ //快速幂取模运算 typedef long long ll; ll modPow(ll x, ll n, ll mod){ ll res = 1; while(n > 0){ if(n & 1 == 1) res = res*x % mod; x = x*x % mod; n = n >> 1; } return res; }