筛质数
利用最小质因子进行判断
if(i % prime[j] == 0) break;
如果i % primes[j]!=0，说明primes[j]不是i的质因子，那么只可能是此时的primes[j]*i的最小质因子,所以primes[j] * i的最小质因子就是primes[j]
如果i % primes[j]==0，说明i的最小质因子是primes[j],因此primes[j]*i的最小质因子也就应该是prime[j]，之后接着用st[primes[j+1]*i]=true去筛合数时，就不是用最小质因子去更新了,因为i具有更小的质因子prime[j]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #include <iostream> using namespace std;const int N = 1e6 + 10 ;bool st[N];int prime[N], cnt;int n;int get_prime () for (int i = 2 ; i <= n; i++) { if (!st[i]) prime[cnt++] = i; for (int j = 0 ; prime[j] <= n / i; j++) { st[prime[j] * i] = true ; if (i % prime[j] == 0 ) break ; } } return cnt; } int main () cin >> n; cout << get_prime (); return 0 ; }
二次筛质数
因为数据最大是\(2^{31}\) ，所以显然不能用线性筛，会TLE
用二次筛：假设一个数n是合数，那么它一定有\(d,\frac{n}{d}\) 两个因子，假设\(d<\frac{n}{d}\) ，则\(d<\sqrt{n}\) ，所以只需要找出\(1\sim\sqrt{n}\) 的所有素数，然后用这些素数更新\([l,r]\) 的所有合数即可
对于素数p，要找到\([l,r]\) 中所有以p为最小质因子的合数，可以从max(2 * p, (l + p - 1) / p * p)开始寻找，然后不断+p即可，其中(l + p - 1) / p * p等价于\(\lceil\frac{l}{p}\rceil\)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 #include <bits/stdc++.h> using namespace std;const int N = 1e6 + 10 ;typedef long long ll;int prime[N], cnt;ll prime2[N], k; bool st[N];void get_prime (int n) for (int i = 2 ; i <= n; i++) { if (!st[i]) prime[cnt++] = i; for (int j = 0 ; prime[j] <= n / i; j++) { st[prime[j] * i] = true ; if (i % prime[j] == 0 ) break ; } } } int main () int l, r; get_prime (50000 ); while (scanf ("%d%d" , &l, &r) != -1 ) { memset (st, 0 , sizeof st); memset (prime2, 0 , sizeof prime2); k = 0 ; for (ll i = 0 ; i < cnt; i++) { ll p = prime[i]; for (ll j = max (2 * p, (l + p - 1 ) / p * p); j <= r; j += p) st[j - l] = true ; } for (int i = 0 ; i <= r - l; i++) { if (!st[i] && i + l > 1 ) prime2[k++] = i + l; } if (k < 2 ) cout << "There are no adjacent primes." << '\n' ; else { int minp = 0 , maxp = 0 ; for (int i = 0 ; i + 1 < k; i++) { int d = prime2[i + 1 ] - prime2[i]; if (d < prime2[minp + 1 ] - prime2[minp]) minp = i; else if (d > prime2[maxp + 1 ] - prime2[maxp]) maxp = i; } printf ("%d,%d are closest, %d,%d are most distant.\n" , prime2[minp], prime2[minp + 1 ], prime2[maxp], prime2[maxp + 1 ]); } } return 0 ; }
阶乘分解
对于8！
1 2 3 4 5 6 7 8
平时的方法是每个数每个数地求，即每一列每一列地求，但是这样的效率太低，于是想到一行一行地求
1 2 3 4 5 6 7 8
1 1 1 1 首先我们\(1\sim
8\) 中2的个数：8 / 2
1 1 然后求出\(1\sim
8\) 中4的个数：8 / 4
1 最后求出\(1\sim
8\) 中8的个数：8 / 8
所以8！中因数2的个数：8 / 2 + 8 / 4 + 8 / 8 = 7
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include <iostream> using namespace std;int prime (int x) if (x == 2 ) return 1 ; for (int i = 2 ; i <= x / i; i++) { if (x % i == 0 ) return 0 ; } return 1 ; } int main () int n; cin >> n; for (int i = 2 ; i <= n; i++) { if (!prime (i)) continue ; long long x = i, ans = 0 ; while (x <= n) ans += n / x, x *= i; cout << i << " " << ans << '\n' ; } return 0 ; }
约数个数
把一个数N写成\(N=p_1 ^ {x_1}\cdot
p_2^{x_2}\cdot ... \cdot p_k^{x_k}\) , 则约数个数为\((x_1+1)(x_2+1)...(x_k+1)\)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #include <iostream> #include <unordered_map> using namespace std;const int mod = 1e9 + 7 ;unordered_map<int , int > mp; typedef long long ll;int main () int n; cin >> n; ll res = 1 ; while (n--) { int a; cin >> a; for (int i = 2 ; i <= a / i; i++) { while (a % i == 0 ) { a /= i; mp[i]++; } } if (a > 1 ) mp[a]++; } for (auto & [x, y] : mp) { res = res * (y + 1 ) % mod; } cout << res; return 0 ; }
约数之和
把一个数N写成\(N=p_1 ^ {x_1}\cdot
p_2^{x_2}\cdot ... \cdot p_k^{x_k}\) , 则约数之和为\(( p_1^0+p_1^1+..._+p_1^{x_1})\times...\times
(p_k^0+p_k^1+...+p_k^{x_k})\)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include <iostream> #include <unordered_map> using namespace std;const int mod = 1e9 + 7 ;unordered_map<int , int > mp; typedef long long ll;int main () int n; cin >> n; while (n--) { int a; cin >> a; for (int i = 2 ; i <= a / i; i++) { while (a % i == 0 ) { a /= i; mp[i]++; } } if (a > 1 ) mp[a]++; } ll res = 1 ; for (auto &[x, y] : mp) { ll t = 1 ; while (y--) { t = (t * x + 1 ) % mod; } res = res * t % mod; } cout << res; return 0 ; }
最大公约数
1 2 3 4 int gcd (int a, int b) return b == 0 ? a : gcd (b, a % b); }
欧拉函数
1∼N 中与 N 互质的数的个数被称为欧拉函数，记为
ϕ(N)。若在算数基本定理中，\(N=p_1^{a_1}p_2^{a_2}…p_m^{a_m}\) ，则：
\(ϕ(N) = N×\frac{p_1 -
1}{p_1}×\frac{p_2−1}{p_2}×…×\frac{p_m−1}{p_m}\)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include <iostream> using namespace std;typedef long long ll;int main () int n; cin >> n; while (n--) { int a; cin >> a; ll res = a; for (int i = 2 ; i <= a / i; i++) { if (a % i == 0 ) res = res / i * (i - 1 ); while (a % i == 0 ) a /= i; } if (a > 1 ) res = res / a * (a - 1 ); cout << res << '\n' ; } return 0 ; }
筛法求欧拉函数
给定一个正整数 n，求 1∼n中每个数的欧拉函数之和。欧拉函数是指\(1\sim N\) 中与N互质的个数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 1. ```i % prime[j] == 0```，在此情况下```prime[j]```是```i```的质因子，所以```i```和```i * prime[j]```的质因子是相同的，所以根据公式，```ph[i * prime[j]] = ph[i] * prime[j]```，即只差N中的```prime[j]``` 2. ```i % prime[j] != 0```，在此情况下```prime[j]```不是```i```的质因子，所以```i```和```i * prime[j]```的质因子相差一个```prime[j]```，所以根据公式，```ph[i * prime[j]] = ph[i] * prime[j] * (1 - 1 / prime[j]) = ph[i] * (prime[j] - 1)```，即差N中的```prime[j]```和质因子的一项```1 - 1 / prime[j]``` ```c++ #include <iostream> using namespace std; const int N = 1e6 + 10; typedef long long ll; ll phi[N], prime[N]; bool st[N]; ll n, cnt; int main() { cin >> n; phi[1] = 1; for(int i = 2; i <= n; i++) { if(!st[i]) { phi[i] = i - 1; prime[cnt++] = i; } for(int j = 0; prime[j] <= n / i; j++) { st[prime[j] * i] = true; if(i % prime[j] == 0) { phi[i * prime[j]] = phi[i] * prime[j]; break; } else phi[i * prime[j]] = phi[i] * (prime[j] - 1); } } ll res = 0; for(int i = 1; i <= n; i++) res += phi[i]; cout << res; return 0; }
快速幂
给定n组\(a_i,b_i,p_i\) ，对于某组数据，求出\(a_i^{b_i}modp_i\)
如果直接暴力枚举，时间复杂度是\(O(b*n)\) ，会TLE
将b用二进制表示，\(b =
2^{x_1}+2^{x_2}+...2^{x_n}\) ；预处理出\(a^{2^0},a^{2^1},...a^{2^{logb}}\)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include <iostream> using namespace std;const int N = 1e5 + 10 ;int n;typedef long long ll;ll qmi (ll a, ll b, ll p) ll ans = 1 ; while (b) { if (b & 1 ) ans = ans * a % p; a = a * a % p; b >>= 1 ; } return ans; } int main () cin >> n; while (n--) { ll a, b, p; cin >> a >> b >> p; cout << qmi (a, b, p) % p << '\n' ; } return 0 ; }
快速幂求逆元
直接根据公式\(b^{m-2}\) 即为b的乘法逆元，求解即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 #include <iostream> using namespace std;const int N = 1e5 + 10 ;typedef long long ll;ll qmi (ll a, ll b, ll p) ll res = 1 ; while (b) { if (b & 1 ) res = res * a % p; a = a * a % p; b >>= 1 ; } return res; } int main () int n; cin >> n; while (n--) { ll a, p; cin >> a >> p; ll res = qmi (a, p - 2 , p); if (a % p == 0 ) cout << "impossible" << '\n' ; else cout << res << '\n' ; } return 0 ; }
