数论专题 1

666DHG 2020-01-18 我要评论

素数

例题：LuoguP3383

暴力（$O(n\sqrt{n})$）

bool Prime[MAXN];

void Check(int n)
  {
    for (int i=1;i<=n;i++)
      {
        if (i<2) continue;
        if (i==2||i==3)
          {
            Prime[i]=true;
            continue;
          }
        for (int j=2;j<=ceil(sqrt(i));j++) if (i%j==0)
          {
            Prime[i]=true;
            break;
          }
        Prime[i]=!Prime[i];
      }
  }

埃式筛法（$O(n\log n)$）

bool vis[MAXN];
int size,prime[MAXN];

void FindPrime(int n)
  {
    vis[0]=vis[1]=true;
    for (int i=2;i<=n;i++) if (!vis[i])
      {
        prime[++size]=i;
        for (int j=2;i*j<=n;j++) vis[i*j]=true;
      }
  }

欧拉筛法（$O(n)$）

bool vis[MAXN];
int size,prime[MAXN];

void FindPrime(int n)
  {
    vis[0]=vis[1]=true;
    for (int i=2;i<=n;i++)
      {
        if (!vis[i]) prime[++size]=i;
        for (int j=1;j<=size&&i*prime[j]<=n;j++)
          {
            vis[i*prime[j]]=true;
            if (i%prime[j]==0) break;
          }
      }
  }

分解质因数

例题：阶乘分解

给定一个数 $N$，分解 $N!$ 的质因数，则有

\[\large{N!=p_{1}^{c1}p_{2}^{c2}p_{3}^{c3}\cdots p_{m}^{cm}}\]

求所有的 $p_{i}$ 与 $c_{i}$。

//http://gdgzoi.com/problem.php?cid=2224&pid=6
#include <bits/stdc++.h>
using namespace std;

const int maxn=1000005;

bool vis[maxn];
int n,ans,size,prime[maxn];

int main()
  {
    scanf("%d",&n);
    //求 1-n 的素数
    vis[0]=vis[1]=true;
    for (int i=2;i<=n;i++)
      {
        if (!vis[i]) prime[++size]=i;
        for (int j=1;j<=size&&i*prime[j]<=n;j++)
          {
            vis[i*prime[j]]=true;
            if (i%prime[j]==0) break;
          }
      }
    //试除法
    for (int i=1;i<=size;i++)
      {
        int now=prime[i];
        ans=0;
        while (n/now!=0)
          {
            ans+=n/now;
            now*=prime[i];
          }
        printf("%d %d\n",prime[i],ans);
      }
    return 0;
  }

欧拉函数

$\phi$($x$) 表示求在 $1 $ 到 $ x$ 的整数中有多少个数与 $x$ 互质

直接求 $\phi$ ($n$) （$O(\sqrt{n})$）

int FindPhi(int n)
  {
    int ans=n;
    for (int i=2;i*i<=n;i++)
      {
        if (n%i==0)
          {
            ans-=ans/i;
            while (n%i==0) n/=i;
          }
      }
    if (n>1) ans-=ans/n;
    return ans;
  }

同时求 $\phi$ ($1$) 到 $\phi$ ($n$)时与 $1$ 到 $n$ 的素数（$O(n)$）

bool vis[MAXN];
int size,Prime[MAXN],Phi[MAXN];

void Find_Phi_and_Prime(int n)  
  {  
    for (int i=2;i<n;i++)  
      {  
        if (!vis[i])  
          {  
            Prime[++size]=i;  
            Phi[i]=i-1;  
          }  
        for (int j=1;j<=size&&i*Prime[j]<n;j++)  
          {  
            vis[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);
          }  
      }  
  }

约数

例题（大数据）：Loj10205

例题（超大数据）：LuoguP2152

辗转相除法

int GCD(int a,int b)
  {
    if (b==0) return a;
    return GCD(b,a%b);
  }

二进制算法

低精

int GCD(int x,int y)
  {
    int i,j;
    if (x==0) return y;
    if (y==0) return x;
    for (i=0;(x&1)==0;i++) x>>=1;
    for (j=0;(y&1)==0;j++) y>>=1;
    if (j<i) i=j;
    while (1)
      {
        if (x<y) x^=y,y^=x,x^=y;
        if ((x-=y)==0) return y<<i;
        while ((x&1)==0) x>>=1;
      }
  }

高精

//https://loj.ac/problem/10205
#include <bits/stdc++.h>
using namespace std;

struct Data
  {
    int a[3005];
    int num;
  };

Data div2(Data x)
  {
    for (int i=x.num;i>=1;i--)
      {
        if (x.a[i]&1) x.a[i-1]+=10;
        x.a[i]>>=1;
        if (!x.a[x.num]) x.num--;
      }
    return x;
  }

bool comp(Data &x,Data &y)
  {
    if (x.num>y.num) return false;
    if (x.num<y.num)
      {
        swap(x.num,y.num);
        for (int i=1;i<=max(x.num,y.num);i++) swap(x.a[i],y.a[i]);
        return false;
      }
    for (int i=x.num;i>=1;i--)
      {
        if (x.a[i]>y.a[i]) return false;
        if (x.a[i]<y.a[i])
          {
            swap(x.num,y.num);
            for (int i=1;i<=max(x.num,y.num);i++) swap(x.a[i],y.a[i]);
            return false;
          }
      }
    return true;
  }

Data plus2(Data x)
  {
    for (int i=1;i<=x.num;i++) x.a[i]<<=1;
    for (int i=1;i<x.num;i++)
      {
        if (x.a[i]>9)
          {
            x.a[i+1]++;
            x.a[i]-=10;
          }
      }
    if (x.a[x.num]>9)
      {
        x.a[x.num+1]=1;
        x.a[x.num]-=10;
        x.num++;
      }
    return x;
  }

Data sub(Data x,Data y)
  {
    for (int i=1;i<=y.num;i++) x.a[i]-=y.a[i];
    for (int i=1;i<x.num;i++)
      {
        if (x.a[i]<0)
          {
            x.a[i+1]--;
            x.a[i]+=10;
          }
      }
    if (x.a[x.num]==0) x.num--;
    return x;
  }

int main()
  {
    Data n,m,ans;
    char c1[3005],c2[3005];
    cin>>c1>>c2;
    n.num=strlen(c1);
    m.num=strlen(c2);
    for (int i=0;i<n.num;i++) n.a[n.num-i]=c1[i]-'0';
    for (int i=0;i<m.num;i++) m.a[m.num-i]=c2[i]-'0';
    int x=0,y=0;
    for (;!(n.a[1]&1);x++) n=div2(n);
    for (;!(m.a[1]&1);y++) m=div2(m);
    if (y<x) x=y;
    while (1)
      {
        if (comp(n,m))
          {
            while (x--) n=plus2(n);
            for (int i=n.num;i>=1;i--) cout<<n.a[i];
            return 0;
          }
        n=sub(n,m);
        while (!(n.a[1]&1)) n=div2(n);
      }
  }

压位高精

//https://loj.ac/problem/10208
//https://www.luogu.com.cn/problem/P2152
//SDOI2009
#include <bits/stdc++.h>
using namespace std;

struct Data
  {
    int a[2005];
    int num;
  };
char c[10005];

void div2(Data &x)
  {
    if (x.a[x.num]==1)
      {
        x.a[x.num-1]+=10000000;
        x.num--;
      }
    for (int i=x.num;i>=1;i--)
      {
        if (x.a[i]&1) x.a[i-1]+=10000000;
        x.a[i]>>=1;
      }
  }

void plus2(Data &x)
  {
    for (int i=1;i<=x.num;i++) x.a[i]<<=1;
    for (int i=1;i<x.num;i++)
      {
        if (x.a[i]>=10000000)
          {
            x.a[i]-=10000000;
            x.a[i+1]++;
          }
      }
    if (x.a[x.num]>=10000000)
      {
        x.a[x.num]-=10000000;
        x.a[x.num+1]=1;
        x.num++;
      }
  }

void sub(Data &x,Data y)
  {
    for (int i=1;i<=y.num;i++) x.a[i]-=y.a[i];
    for (int i=1;i<x.num;i++)
      {
        if (x.a[i]<0)
          {
            x.a[i+1]--;
            x.a[i]+=10000000;
          }
      }
    if (x.a[x.num]==0) x.num--;
  }

bool comp(Data &x,Data &y)
  {
    if (x.num>y.num) return false;
    if (x.num<y.num)
      {
        swap(x.num,y.num);
        for (int i=1;i<=max(x.num,y.num);i++) swap(x.a[i],y.a[i]);
        return false;
      }
    for (int i=x.num;i>=1;i--)
      {
        if (x.a[i]>y.a[i]) return false;
        if (x.a[i]<y.a[i])
          {
            swap(x.num,y.num);
            for (int i=1;i<=max(x.num,y.num);i++) swap(x.a[i],y.a[i]);
            return false;
          }
      }
    return true;
  }

int main()
  {
    Data n,m;
    int stop,x,y,t,cnt;
    scanf("%s",c);
    for (int i=strlen(c)-1;i>=0;i-=7)
      {
        n.num++;
        n.a[n.num]=0;
        stop=max(i-6,0);
        for (int j=i;j>=stop;j--) n.a[n.num]+=(c[j]-'0')*pow(10,i-j);
      }
    scanf("%s",c);
    for (int i=strlen(c)-1;i>=0;i-=7)
      {
        m.num++;
        m.a[m.num]=0;
        stop=max(i-6,0);
        for (int j=i;j>=stop;j--) m.a[m.num]+=(c[j]-'0')*pow(10,i-j);
      }
    for (x=0;!(n.a[1]&1);x++) div2(n);
    for (y=0;!(m.a[1]&1);y++) div2(m);
    if (y<x) x=y;
    while (1)
      {
        if (comp(n,m)) 
          {
            while(x--) plus2(n);
            printf("%d",n.a[n.num]);
            for (int i=n.num-1;i>=1;i--)
              {
                t=n.a[i];
                cnt=0;
                while (t/10) t/=10,cnt++;
                for (int i=1;i<7-cnt;i++) printf("0");
                printf("%d",n.a[i]);
              }
            return 0;
          }
        sub(n,m);
        while (!(n.a[1]&1)) div2(n);
      }
    return 0;
  }

乘法逆元

例题：LuoguP3383

解决的问题

求下面关于 $x$ 的同余方程的整数解

\[\large ax\equiv 1\text{ }(\text{ }mod\text{ }\text{ }b\text{ })\]

欧几里得（拓展）

可以将上面的同余方程化为

\[\large ax=1-by\]

\[\large ax+by=1\]

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);
    long long t=x;
    x=y;
    y=t-(a/b)*y;
    return r;
  }

快速幂

这里需要用到费马小定理

若 $a$ 为正整数，$b$ 为素数，$a,b$ 互质，则有
\[\large a^{b-1}\equiv 1(\text{ }mod\text{ }\text{ }b\text{ })\]

把这个式子代入 $ax\equiv 1\text{ }(\text{ }mod\text{ }\text{ }b\text{ })$ 中，得

\[\large ax\equiv a^{b-1}\text{ }(\text{ }mod\text{ }\text{ }b\text{ })\]

\[\large x\equiv a^{b-2}\text{ }(\text{ }mod\text{ }\text{ }b\text{ })\]

所以这时候方程的解就是 $a^{b-2}\text{ }(\text{ }mod\text{ }\text{ }b\text{ })$

long long fastpow(long long a,long long b,long long p) //a^b%p
  {
    if (b==0) return 1;
    if (b==1) return a%p;
    long long half=fastpow(a,b/2,p);
    if (b&1) return ((half%p*half%p)%p*a)%p;
    return (half%p*half%p)%p;
  }
  
int main()
  {
    //...
    long long x=fastpow(a,b-2,b);
    //...
  }

线性算法求 $1$ 到 $n$ 模 $b$ 的逆元（$O(n)$）

inv[1]=1;
for (int i=2;i<=n;i++)
    inv[i]=(p-p/i)*inv[p%i]%p;

数论专题 1

目录

素数

例题：LuoguP3383

暴力（\(O(n\sqrt{n})\)）

埃式筛法（\(O(n\log n)\)）

欧拉筛法（\(O(n)\)）

分解质因数

例题：阶乘分解

欧拉函数

直接求 \(\phi\) (\(n\)) （\(O(\sqrt{n})\)）

同时求 \(\phi\) (\(1\)) 到 \(\phi\) (\(n\))时与 \(1\) 到 \(n\) 的素数（\(O(n)\)）

约数

例题（大数据）：Loj10205

例题（超大数据）：LuoguP2152

辗转相除法

二进制算法

乘法逆元

例题：LuoguP3383

解决的问题

欧几里得（拓展）

快速幂

线性算法求 \(1\) 到 \(n\) 模 \(b\) 的逆元（\(O(n)\)）

相关文章

猜您喜欢

今日热门

数论专题 1

目录

素数

例题：LuoguP3383

暴力 （\(O(n\sqrt{n})\)）

埃式筛法 （\(O(n\log n)\)）

欧拉筛法 （\(O(n)\)）

分解质因数

例题：阶乘分解

欧拉函数

直接求 \(\phi\) (\(n\)) （\(O(\sqrt{n})\)）

同时求 \(\phi\) (\(1\)) 到 \(\phi\) (\(n\))时与 \(1\) 到 \(n\) 的素数 （\(O(n)\)）

约数

例题（大数据）：Loj10205

例题（超大数据）：LuoguP2152

辗转相除法

二进制算法

乘法逆元

例题：LuoguP3383

解决的问题

欧几里得（拓展）

快速幂

线性算法求 \(1\) 到 \(n\) 模 \(b\) 的逆元 （\(O(n)\)）

相关文章

猜您喜欢

今日热门

暴力（\(O(n\sqrt{n})\)）

埃式筛法（\(O(n\log n)\)）

欧拉筛法（\(O(n)\)）

同时求 \(\phi\) (\(1\)) 到 \(\phi\) (\(n\))时与 \(1\) 到 \(n\) 的素数（\(O(n)\)）

线性算法求 \(1\) 到 \(n\) 模 \(b\) 的逆元（\(O(n)\)）