数学专题

· · 个人记录

基础算法/定理

  1. 质数相关

    • 线性筛 
      const int maxp = 100000001;
int pr[maxp], prime[maxp], top = 0;
inline void getPrime(int maxprime)
{
  pr[1] = 1;
  for (int i = 2; i <= maxprime; i++)
  {
      if (!pr[i]) prime[++top] = i;
      for (int j = 1; j <= top && 1ll * i * prime[j] <= maxprime; j++)
      {
          pr[i * prime[j]] = prime[j];
          if (!(i % prime[j])) break;
      }
  }
}
      ``` while (x > 1) { ++num; if (pr[x] <= 1) break; x /= pr[x]; } ```

  2. exgcd扩展欧几里德
    用来求ax+by=gcd(a,b)的一组整数解。
    推导过程：

    ax+by=gcd(a,b) =gcd(b,a\%b) =bx'+(a\%b)y' =bx'+(a-b* \lfloor{a\over b}\rfloor)y' =ay'+b(x'-\lfloor{a\over b}\rfloor y')

    这样就珂以推出x=y',y=x'-\lfloor{a\over b}\rfloor y'这一答案了。
    然后方程就转变成了去求解bx'+(a\%b)y'=gcd(b,a\%b)了
    然后我们把b当作新的a，a\%b当作新的b，递归去计算，最后总能得到bx'+a\%by'=gcd(b,a\%b)=b，也就是bx'+0y'=b的情况，这时候x'也就是上一个方程中的y的值就是1，而y'的值任意，出于习惯，一般使y'=0，其实y'取任何值都是珂以的，只是最后算出来x的大小不同而已，但是都满足最初的线性同余方程。而在求逆元等运算中，算出来的x要取模，取模以后的值都是一样的。
    code:

    #include<bits/stdc++.h>
using  namespace std;
long long m,n;
long long exgcd(long long a,long long b,long long &x,long long &y)
{
  if(!b)
  {
      x=1,y=0;
      return a;
  }
  long long r=exgcd(b,a%b,x,y),t=x;
  x=y,y=t-a/b*y;
  return r;
}
int main()
{
  scanf("%lld%lld",&m,&n);
  long long x,y;
  long long gcd=exgcd(m,n,x,y);
  printf("%lld %lld %lld",gcd,x,y);
  return 0;
}

    那么就可以用扩展欧几里德去解线性同余方程了。
    对于方程ax+by=c,它就等价于ax\equiv c (mod b),而上面的式子珂化为：ax\equiv gcd(a,b) (mod b)，那么两个方程的结果就相差c/gcd(a,b)倍，如果不满足gcd(a,b)|c，那么ax+by=c无整数解。
    但是我们在实际应用的过程中用到的一般是ax\equiv gcd(a,b) (mod b)的解的最小值，因此我们珂以通过x=(x\%t+t)\%t, t=b/gcd(a,b)来求出最小正整数解，这里首先让x\%t，使x保证-t<x<t，然后+t，让x保证0<x<2t,最后再%t,就珂以保证0\leq x<t。
    比如P1516 青蛙的约会，这题，开始我就不会求最小正整数解，结果错了orz。

  3. 卢卡斯定理

    C_n^m=C_{n\%p}^{m\%p}*C_{\lfloor \frac{n}{p} \rfloor}^{\lfloor \frac{m}{p} \rfloor}\pmod p

    另一种版本：
    设p_k=p^k,m={a_0}^{p_0}+{a_1}^{p_1}+\cdots+{a_k}^{p_k},n={b_0}^{p_0}+{b_1}^{p_1}+\cdots+{b_k}^{p_k}

    C_m^n\equiv\prod{C_{a_i}^{b_i}}(mod~p)

    意义就是吧m和n表示成p进制下的数，然后让这些数的每一位对应的C相乘。
    洛谷上有模板题，代码以后再说。

  4. 欧拉定理
    若a与n互质，那么a^{\phi(n)}\equiv 1 \pmod n，
    其中\phi(n) 表示1~n-1中与n互质的数的个数。

  5. 求约数个数

    • O(n\sqrt n) 
      inline int appr(int n)
{
  register int i,ans=0;
  for(i=1;i*i<n;i++)ans++;
  ans<<=1;
  if(i*i==n)ans++;
  return ans;
}
    • O(nlogn)

      巧妙地运用了打表的思想 

      inline int appr(int n)
{
  for(register int i=1;i<=n;i++)
    for(register int j=i;j<=n;j+=i)
        d[j]++;
  return d[n];
}

  6. 费马定理
    若a与p互质，则满足a^{p-1}\equiv1\pmod p

  7. 求逆元(求a在模p意义下的逆元，保证a、p互质)

    • 扩展欧几里德 ax+py=1$等价于$ax\equiv1\pmod p$,把a除过来，就得到了$x\equiv a^{-1}\pmod p$,因此我们珂以通过求$ax+py=1$的解x，来求出$a^{-1} 
      #include<cstdio>
#include<cstring>
#include<iostream>
long long n,p,x,y;
long long exgcd(long long a,long long b,long long &x,long long &y)
{
  if(b==0)
  {
    x=1,y=0;
    return a;
  }
  long long r=exgcd(b,a%b,x,y),t=x;
  x=y;
  y=t-a/b*y;
  return r;
}
int main()
{
  scanf("%lld%lld",&n,&p);
  exgcd(n,p,x,y);
  printf("%lld\n",((x%p)+p)%p);
}
    • 费马定理
      因为a、p互质,因此a^{p-1}\equiv1\pmod p成立，因此a^{p-2}\equiv a^{-1}\pmod p成立，于是乎用快速幂求出a^{p-2} \mod p即可求出a^{-1} 
      #include<cstdio>
long long n,p;
inline long long power(long long x,long long p,long long mod)
{
    if(x==1)return 1;
    long long ans=1;
    while(p)
    {
        if(p&1)ans=ans*x%mod;
        x=x*x%mod;
        p>>=1;
    }
    return ans;
}
long long inv(long long x,long long mod){ return power(x,mod-2,mod); }
int main()
{
    scanf("%lld%lld",&n,&p);
    printf("%lld\n",inv(n, p);
}
    • 线性递推
      推导：
      由p=\lfloor {p\over a}\rfloor*a+p\mod a
      得：\lfloor {p\over a}\rfloor*a+p\mod a\equiv 0 \pmod p
      两侧同时除以a和p\mod a,得： \lfloor {p\over a}\rfloor*(p\mod a)^{-1}+a^{-1}\equiv 0 \pmod p

      即a^{-1}\equiv -\lfloor {p\over a}\rfloor*(p\mod a)^{-1} \pmod p
      然后为了使求出来的值为正方便取模，再加上p（加的位置非常巧妙）

      a^{-1}\equiv (p-\lfloor {p\over a}\rfloor)*(p\mod a)^{-1} \pmod p

      这样就得到了递推式：(inv[i]表示i在模p意义下的逆元)

      inv[i]=(p-p/i)*inv[p\%i]\%p

      然后就珂以O(n)线性求逆元啦！
      当然，也珂以实现O(nlogn)求单个数的逆元。 

      #include<cstdio>
#include<cstring>
#include<iostream> 
#include<algorithm>
const int maxn=3e6+7;
long long n,p,inv[maxn];
int main()
{
  scanf("%lld%lld",&n,&p);
  puts("1");
  inv[1]=1;
  for(register int i=2;i<=n;i++)
  {
      inv[i]=(p-p/i)*inv[p%i]%p;
      printf("%lld\n",inv[i]);
  }
  return 0;
}

多项式算法