数论 Level1
说明
- 内容量过大，只保留自己不太会的部分
qwq
整除
-
辗转相除法时间复杂度为 O(\log n)
-
O(n^{\frac{1}{4}}) 的分解质因数 \to\ \ pollard\ rho
-
1 至 n 大约有 \frac{n}{\log n} 个质数
-
线性筛质数：考虑让每个数仅被其最小质因子筛除
- （是
p[++ cnt] = i;）qwq
取模
- 把$\mod p$ 看成一个数域设\ p=7\\ 3+5=1\pmod 7
-
怎么在模意义下定义除法？
a/b=c\\ 如果b*c=a则说明a/b=c\pmod p -
当 \gcd(g,p) = 1 时 g 在模 p 意义下才有逆元
-
如果让你求 C^m_n\mod p 且 p 不为质数？
-
先把 p 质因数分解，挨个取模然后用 CRT 把答案缩到一起
逆元
-
如何求逆元？
-
单个逆元：快速幂（欧拉定理、费马小定理）
-
预处理多个逆元：线性筛、线性递推
-
预处理阶乘逆元
-
费马小定理：若 p 为质数，且 a 不为 p 的倍数，则 a^{p-1}\equiv 1\pmod p
-
a^{p-2} 即为模 p 意义下的逆元（前提是 p 为质数）
-
Miller-Rabin 素性检验：
- 欧拉函数：\phi(n)=\sum^n_{i=1}[\gcd(i,n)=1]
- 即 [1,n] 中和 n 互质的数的个数
- 若 p 是质数，则 \phi(p)=p-1
- 一个函数 f(n) 是积性函数，当且仅当对于任意一对互质正整数 n,m ，都有 f(nm)=f(n)f(m)
- 可以证明欧拉函数是积性函数
- 一切积性函数均可线性筛
- 性质：
- 若 \gcd(a,n) = 1 ，则 a^{\phi(n)}\equiv 1\pmod n
- 当 n 为质数时，可得费马小定理
- 由裴蜀定理我们知道必然存在 x,y 使得 ax + by = \gcd(a,b)
- 可以用辗转相除法求出一组 x,y
-
考虑在回溯过程中不断求出上一层的 x 和 y
-
相邻两层为：
ax_1+by_1=\gcd(a,b)\\ bx_2+(a\ \operatorname{mod}\ b)y_2=\gcd(a,b) -
联立解得 x_1 = y_2,y_1=x_2-ry_2 ，其中$r=\lfloor a/b\rfloor$
-
exgcd模板：int exgcd(int a,int b,int &x,int &y) { if (b == 0) { x = 1, y = 0; return a; } int g = exgcd(b,a%b,y,x); y -= a / b * x; return g; } -
怎么求逆元？
ax = 1 \pmod b\\ ax+ay=1\ 求 x -
若 a 和 p 互质，则存在 ax + by = 1 ，即 ax \equiv 1 \pmod p
-
求出 [0,p) 之间的 x 即为 a 在模 p 意义下的逆元
-
还有一种更方便的求逆元的方法：
inv[i] = (p-p/i)*inv[p\%i]\%p -
可以线性复杂度预处理 n 以内的逆元
-
也可以写成递归的形式 O(\log n) 求出单个数的逆元
中国剩余定理 (CRT)
- 问题原型：
-
对于一元线性同余方程组
(S_1):\left\{ \begin{matrix} x\equiv a_1\pmod {m_1} \\x\equiv a_2\pmod {m_1} \\\vdots \\x\equiv a_n\pmod{m_n} \end{matrix}\right. -
当整数 m_1,m_2,\dots,m_n 两两互质时，则对于任意整数 a_1,a_2,\dots,a_n ，方程组 (S_1) 有解
-
构造方法：
课后题
快速求质数
-
超级水但是一定要记住特判 1 不是质数！！！！！！！！！！
qwq -
直接暴力求质数
#include<bits/stdc++.h> #define ll long long using namespace std; ll n,m; bool check(ll x) { if (x == 1) return false; if (x == 2) return true; for (ll i = 2;i * i <= x;i ++) if (x % i == 0) return false; return true; } int main() { scanf("%lld%lld",&n,&m); for (ll i = n;i <= m;i ++) if (check(i)) printf("%lld ",i); return 0; }
一道大水题
-
正如其名 -
第一眼好像边数会爆炸啊
-
看这一句话:
第 i 个点到第 j 个点有边当且仅当 j 是 i 的倍数且 j/i 为质数。
-
也就是说 j/i 是 i 的质因子时 i,j 之间有连边
-
1 到 n 范围内的质数大约在 \log n 级别
-
所以边数也就 \log n 条边
-
然后就边筛质数边更新答案
#include<bits/stdc++.h> #define int long long using namespace std; const int maxn = 500005,P = 1e9 + 7; int n,q,p[maxn],tot,f[maxn]; bool vis[maxn]; signed main() { scanf("%lld%lld",&n,&q); for (int i = 2;i <= n;i ++) { if (!vis[i]) p[++ tot] = i; for (int j = 1;i * p[j] <= n && j <= tot;j ++) { vis[i * p[j]] = true; if (i % p[j] == 0) break; } } for (int i = 1;i <= tot;i ++) f[p[i]] = 1; for (int i = 2;i <= n;i ++) for (int j = 1;i * p[j] <= n && j <= tot;j ++) f[i * p[j]] = (f[i * p[j]] + f[i]) % P; // 是质因数 -> 转移答案 for (int i = 1,x;i <= q;i ++) { scanf("%lld",&x); printf("%lld\n",f[x]); } }
千鸽笼
-
题目给了要用
并查集的提示那咱就用呗 -
枚举 [\max(a,p),b] 中的质数，以这个质数为质因子去合并鸽笼
-
合并鸽笼的过程就可以用并查集维护
#include <bits/stdc++.h> #define ll long long #define int ll using namespace std; const int maxn = 1e7 + 10; ll l, r, p, cnt, sz[maxn]; ll fa[maxn]; int query(int x) { return fa[x] == x ? x : fa[x] = query(fa[x]); } void Union(int x,int y) { x = query(x), y = query(y); if (sz[x] <= sz[y]) fa[x] = y; else fa[y] = x; if (sz[x] == sz[y]) sz[x] ++; } bool check(int x) { if (x < 2) return false; if (x == 2) return true; for (int i = 2; i * i <= x; i++) if (x % i == 0) return false; return true; } signed main() { scanf("%lld%lld%lld",&l,&r,&p); for (int i = 1;i < maxn;i ++) fa[i] = i; for (; p <= r; p++) if (check(p)) for (ll i = p; i + p <= r; i += p) { if (i < l) continue; if (query(i) != query(i + p)) { cnt++; Union(i,i + p); } } printf("%lld",r - l + 1 - cnt); }
质因子分解
-
这真的没啥好说的，从 1 到 n 挨个拆就行了
qwq#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn = 1e4 + 5; int n; ll p[maxn],tot,ans[maxn]; bool vis[maxn]; int main() { scanf("%d",&n); for (int i = 2;i <= n;i ++) { // 把素数都求出来备用 if (!vis[i]) p[++ tot] = i; for (int j = 1;i * p[j] <= n && j <= tot;j ++) { vis[j] = true; if (i % p[j] == 0) break ; } } for (int i = 2;i <= n;i ++) { int x = i; for (int j = 1;j <= tot;j ++) while (x > 1 && x % p[j] == 0) x /= p[j], ans[p[j]] ++; } for (int i = 1;i <= tot;i ++) if (ans[p[i]]) printf("%d %d\n",p[i],ans[p[i]]); return 0; }
5的倍数的个数
-
这个题就有点难度
-
考虑单独一个 a 串的情况，假设第 i 位上的数字为 0 或 5 ，就说明只要把 [i+1,n] 全部删光，这个串就是 5 的倍数
-
[1,i-1] 这段区间里的数删不删随意，每个数要么删要么不删，就会对答案产生 2^{i-1} 的贡献
-
再考虑 k 个 a 的情况，假设单独一个串 a 对答案的总贡献为 A ，则 aa 就会对答案产生 A + 2^n\times A 的贡献，其中 n 表示 a 的长度，相当于把第一个 a 中的每个数字都删或不删，总共就是 2^n 次方种情况，再用乘法原理乘上第二个 a 中的情况
-
以此类推，就会得到一个等比数列：
S = A+2^n\times A + 2^{2n}\times A + 2^{3n}\times A + \dots + 2^{kn}\times A -
用一下等比数列求和公式：
S = \frac{A(2^{nk}-1)}{2^n-1} -
因为有除法运算，所以需要求出逆元，我用的费马小定理去求
-
记住能取模一定取模，能
long long一定long long！#include<bits/stdc++.h> #define ll long long #define int long long using namespace std; const int P = 1e9 + 7,maxn = 1e6 + 5; char c[maxn]; int k,n; ll A,ans; ll qp(ll x,ll y) { ll res = 1; while (y > 0) { if (y & 1) res = (res * x) % P; x = (x * x) % P, y >>= 1; } return res % P; } signed main() { scanf("%s",c + 1); scanf("%lld",&k); n = strlen(c + 1); for (int i = 1;i <= n;i ++) if (c[i] == '5' || c[i] == '0') A = (A % P + qp(2,i - 1) % P) % P; ans = ((((A % P) * (qp(2,n * k) % P - 1) % P) % P) % P) * ((qp((qp(2,n) % P - 1) % P,P - 2) % P) % P) % P; printf("%lld",(ans % P + P) % P); }
