数论基础算法整理总结 以前学习的做的笔记，现在整理一下发出来 一些概念 算术基本定理 费马定理 其他 快速幂 欧几里得求最大公约数 扩展欧几里得 中国剩余定理 欧拉函数和欧拉定理 线性基 定义 性质 插入 合并 查询 k小值 BM杜教筛 一些概念 算术基本定理 一个大于1的正整数 $N$，如果它的标准分解式为：$N = P^1_{a1} P^2_{a2}…P^n_{an}$，那么它的正因数个数为 $ \sigma_{0}(N) = (1+a_{1})(1+a_{2})...(1+a_{n}) $. 它的全体正因数之和为 $ \sigma_{1}(N) = (1+p_{1}+ p_{1}^{2}+...+ p_{1}^{a1})(1+p_{2}+ p_{2}^{2}+...+ p_{2}^{a2})...(1+p_{n}+ p_{n}^{2}+...+ p_{n}^{an}) $ 当 $ \sigma_{0}(N) = 2n $ 时就称 $N$ 为完全数。 是否存在奇完全数，是一个至今未解决之猜想。 利用算术基本定理可以重新定义整数 $a$ 和 $b$ 的最大公因子 $(a, b)$ 和最小公倍数 $[a, b]$，并证明 $ab = (a, b) × [a, b]$。 此外还可证明根号2是无理数等等。 证明素数个数无限。 费马定理 费马大定理：当 $n ≥ 2$ 时，关于$ x, y, z $的方程 $x^n + y^n = z^n$ 没有正整数解。 费马小定理： 假如 $p$ 是质数，且 $gcd(a, p)=1$，那么 $a^{p-1} ≡ 1（mod p）$，即：假如 $a$ 是整数，$p$ 是质数，且 $a, p$ 互质(即两者只有一个公约数1)，那么 $a$ 的 $(p-1)$ 次方除以 $p$ 的余数恒等于1。 其他 调和级数(即f(n))至今没有一个完全正确的公式，但欧拉给出过一个近似公式：(n很大时，n小的时候暴力) $f(n)≈ln(n)+C+1/2*n ( f(n)= 1/1 + 1/2 + 1/3 + … + 1/n )$ 欧拉常数值：$C≈0.57721566490153286060651209$ c++ math库中，log即为ln。 快速幂 ll pow(ll a, ll b) { ll result = 1; ll base = a; while (b) { if (b & 1) result *= base; base *= base; b >>= 1; } return result; } ll powmod(ll a, ll b, ll c) { //取模 ll result = 1; ll base = a % c; while (b) { if (b & 1) result = (result * base) % c; base = (base * base) % c; b >>= 1; } return result; } 欧几里得求最大公约数 ll gcd(ll a, ll b) { if (!b) return a; return gcd(b, a % b); } 扩展欧几里得 long long extend_gcd(long long a, long long b, long long &x, long long &y) { //求 ax + by = gcd(a, b) 的解 if (a == 0 && b == 0) return -1; //最大公约数不存在 if (b == 0) { x = 1, y = 0; return a; } long long r = extend_gcd(b, a % b, y, x); y -= x * (a / b); return r; } long long mod_inv(long long a, long long n) { //求逆元 long long x, y; long long d = extend_gcd(a, n, x, y); if (d == 1) return (x % n + n) % n; else return -1; } 中国剩余定理 //n个方程：x=a[i](mod m[i]) (0<=i<n) ll china(int n, ll *a, ll *m){ ll M = 1, ret = 0; for(int i = 0; i < n; i ++) M *= m[i]; for(int i = 0; i < n; i ++){ ll w = M / m[i]; ret = (ret + w * mod_inv(w, m[i]) * a[i]) % M; } return (ret + M) % M; } 欧拉函数和欧拉定理 定义：对正整数 n, 欧拉函数是小于 n 的正整数中与 n 互质的数的数目（φ(1)=1） 性质 : 对于质数 p, φ(p)=p−1 若p为质数, n=pk, 则 φ(n)=pk-pk-1 欧拉函数是积性函数, 但不是完全积性函数。若 m, n 互质, 则 φ(m∗n)=φ(m)∗φ(n) 特殊的, 当 m=2,n 为奇数时，φ(2*n)=φ(n) 当 n>2 时, φ(n)是偶数 小于 n 的数中, 与 n 互质的数的总和为：φ(n) * n / 2 (n>1) n=∑d∣nφ(d)，即n的因数 (包括 1 和它自己) 的欧拉函数之和等于 n (1) 求单个变量的欧拉函数 long long eular(long long x) { int res = x, a = x; for (int i = 2; i * i <= a; i++) { if (a % i == 0) { res = res / i * (i - 1); //res -= res/i; while (a % i == 0) a /= i; } } if(a > 1) res = res / a * (a - 1); //res -= res/a; return res; } (2) 欧拉表 int euler[Max]; void euler(void) { euler[1] = 1; for (int i = 2; i < Max; i++) euler[i] = i; for (int i = 2; i < Max; i++) if (euler[i] == i) for (int j = i; j < Max; j += i) euler[j] = euler[j] / i * (i - 1); //先进行除法是为了防止中间数据的溢出 } (3) 线性筛 (同时得到欧拉函数和素数表) const int MAXN = 10000000; bool check[MAXN + 10]; int phi[MAXN + 10]; int prime[MAXN + 10]; int tot; //素数的个数 void phi_and_prime_table(int N) { memset(check, false, sizeof(check)); phi[1] = 1; tot = 0; for (int i = 2; i <= N; i++) { if (!check[i]) { prime[tot++] = i; phi[i] = i - 1; } for (int j = 0; j < tot; j++) { if (i * prime[j] > N) break; check[i * prime[j]] = 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); } } } } 线性基 定义 设数集T的值域范围为[1, 2n−1]。 T的线性基是T的一个子集A={a1, a2, a3, ..., an}。 A中元素互相xor所形成的异或集合，等价于原数集T的元素互相xor形成的异或集合。 可以理解为将原数集进行了压缩。 性质 设线性基的异或集合中不存在0。 线性基的异或集合中每个元素的异或方案唯一，其实这个跟性质1是等价的。 线性基二进制最高位互不相同。 如果线性基是满的，它的异或集合为[1, 2n−1]。 线性基中元素互相异或，异或集合不变。 插入 如果向线性基中插入数x，从高位到低位扫描它为1的二进制位。 扫描到第i时，如果ai不存在，就令ai = x，否则x = x⊗ai。 x的结局是，要么被扔进线性基，要么经过一系列操作过后，变成了0。 bool insert(long long val) { for (int i = 60; i >= 0; i--) if (val & (1LL << i)) { if (!a[i]) { a[i] = val; break; } val ^= a[i]; } return val > 0; } 合并 将一个线性基暴力插入另一个线性基即可 L_B merge(const L_B& n1, const L_B& n2) { L_B ret = n1; for (int i = 0; i <= 60; i++) if (n2.d[i]) ret.insert(n2.d[i]); return ret; } 查询   如果要查询x是否存于异或集合中。   从高位到低位扫描x的为1的二进制位。   扫描到第i位的时候x=x⊗ai   如果中途x变为了0，那么表示x存于线性基的异或集合中。   从高位到低位扫描线性基。   如果异或后可以使得答案变大，就异或到答案中去。 long long query_max() { long long ret = 0; for (int i = 60; i >= 0; i--) if ((ret ^ d[i]) > ret) ret ^= d[i]; return ret; } 最大值   最小值即为最低位上的线性基 long long query_min() { for (int i = 0; i <= 60; i++) if (d[i]) return d[i]; return 0; } k小值 根据性质3。 我们要将线性基改造成每一位相互独立。 具体操作就是如果i < j，aj的第i位是1，就将aj异或上ai。 经过一系列操作之后，对于二进制的某一位i。只有ai的这一位是1，其他都是0。 所以查询的时候将k二进制拆分，对于1的位，就异或上对应的线性基。 最终得出的答案就是k小值。 void rebuild() { for (int i = 60; i >= 0; i--) for (int j = i - 1; j >= 0; j--) if (d[i] & (1LL << j)) d[i] ^= d[j]; for (int i = 0; i <= 60; i++) if (d[i]) p[cnt++] = d[i]; } long long kthquery(long long k) { int ret = 0; if (k >= (1LL << cnt)) return -1; for (int i = 60; i >= 0; i--) if (k & (1LL << i)) ret ^= p[i]; return ret; } 最终板子如下 struct L_B { long long d[61], p[61]; int cnt; L_B() { memset(d, 0, sizeof(d)); memset(p, 0, sizeof(p)); cnt = 0; } bool insert(long long val) { for (int i = 60; i >= 0; i--) if (val & (1LL << i)) { if (!d[i]) { d[i] = val; break; } val ^= d[i]; } return val > 0; } long long query_max() { long long ret = 0; for (int i = 60; i >= 0; i--) if ((ret ^ d[i]) > ret) ret ^= d[i]; return ret; } long long query_min() { for (int i = 0; i <= 60; i++) if (d[i]) return d[i]; return 0; } void rebuild() { for (int i = 60; i >= 0; i--) for (int j = i - 1; j >= 0; j--) if (d[i] & (1LL << j)) d[i] ^= d[j]; for (int i = 0; i <= 60; i++) if (d[i]) p[cnt++] = d[i]; } long long kthquery(long long k) { int ret = 0; if (k >= (1LL << cnt)) return -1; for (int i = 60; i >= 0; i--) if (k & (1LL << i)) ret ^= p[i]; return ret; } } L_B merge(const L_B & n1, const L_B & n2) { L_B ret = n1; for (int i = 60; i >= 0; i--) if (n2.d[i]) ret.insert(n1.d[i]); return ret; } BM杜教筛 #include <bits/stdc++.h> using namespace std; #define rep(i,a,n) for (long long i=a;i<n;i++) #define per(i,a,n) for (long long i=n-1;i>=a;i--) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((long long)(x).size()) typedef vector<long long> VI; typedef long long ll; typedef pair<long long,long long> PII; const ll mod=1e9+7; ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} // head long long _,n; namespace linear_seq { const long long N=10010; ll res[N],base[N],_c[N],_md[N]; vector<long long> Md; void mul(ll *a,ll *b,long long k) { rep(i,0,k+k) _c[i]=0; rep(i,0,k) if (a[i]) rep(j,0,k) _c[i+j]=(_c[i+j]+a[i]*b[j])%mod; for (long long i=k+k-1;i>=k;i--) if (_c[i]) rep(j,0,SZ(Md)) _c[i-k+Md[j]]=(_c[i-k+Md[j]]-_c[i]*_md[Md[j]])%mod; rep(i,0,k) a[i]=_c[i]; } long long solve(ll n,VI a,VI b) { // a 系数 b 初值 b[n+1]=a[0]*b[n]+... //printf("%d\n",SZ(b)); ll ans=0,pnt=0; long long k=SZ(a); assert(SZ(a)==SZ(b)); rep(i,0,k) _md[k-1-i]=-a[i];_md[k]=1; Md.clear(); rep(i,0,k) if (_md[i]!=0) Md.push_back(i); rep(i,0,k) res[i]=base[i]=0; res[0]=1; while ((1ll<<pnt)<=n) pnt++; for (long long p=pnt;p>=0;p--) { mul(res,res,k); if ((n>>p)&1) { for (long long i=k-1;i>=0;i--) res[i+1]=res[i];res[0]=0; rep(j,0,SZ(Md)) res[Md[j]]=(res[Md[j]]-res[k]*_md[Md[j]])%mod; } } rep(i,0,k) ans=(ans+res[i]*b[i])%mod; if (ans<0) ans+=mod; return ans; } VI BM(VI s) { VI C(1,1),B(1,1); long long L=0,m=1,b=1; rep(n,0,SZ(s)) { ll d=0; rep(i,0,L+1) d=(d+(ll)C[i]*s[n-i])%mod; if (d==0) ++m; else if (2*L<=n) { VI T=C; ll c=mod-d*powmod(b,mod-2)%mod; while (SZ(C)<SZ(B)+m) C.pb(0); rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod; L=n+1-L; B=T; b=d; m=1; } else { ll c=mod-d*powmod(b,mod-2)%mod; while (SZ(C)<SZ(B)+m) C.pb(0); rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod; ++m; } } return C; } long long gao(VI a,ll n) { VI c=BM(a); c.erase(c.begin()); rep(i,0,SZ(c)) c[i]=(mod-c[i])%mod; return solve(n,c,VI(a.begin(),a.begin()+SZ(c))); } }; int main() { while(~scanf("%lld", &n)) { printf("%lld\n",linear_seq::gao(VI{1,5,11,36,95,281,781,2245,6336,18061, 51205},n-1)); } }