以前学习的做的笔记，现在整理一下发出来

一些概念

算术基本定理

一个大于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)=p^k-p^k-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, 2ⁿ−1]。
T的线性基是T的一个子集A={a1, a2, a3, ..., an}。
A中元素互相xor所形成的异或集合，等价于原数集T的元素互相xor形成的异或集合。
可以理解为将原数集进行了压缩。

性质

设线性基的异或集合中不存在0。
线性基的异或集合中每个元素的异或方案唯一，其实这个跟性质1是等价的。
线性基二进制最高位互不相同。
如果线性基是满的，它的异或集合为[1, 2ⁿ−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));
    }
}

数论基础算法整理总结