学习笔记:日照day6数论总(meng)结(bi)

xjb谈一谈

日照一中day6了….lsr&&hcy的水痘让人心慌慌…还有我为什么没带手机||笔记本嘞???上(tui)课(fei)的时候摆弄老年机可真是….
但是大丈夫啊,我有老婆啊(划掉)

唯一分解定理

一个合数(>1)可以分成一堆质数(有重复)的积,记为x=π p[i]^a[i] p为x的质因子,a[i]为p[i]的个数(没有为0)上面这个优雅的式子被称为x的标准分解式

埃氏筛法

筛法用于求一堆素数;
筛法是基于一个显而易见的道理:素数没有比她小的因子,这也是朴素求素数算法的基础(枚举2~sqrt(n))朴素算法是有一个数,然后判断她是否是素数,求一个范围的素数显然爆炸,那么推广一下,如何求一堆素数嘞?筛法啊QAQ
埃氏筛法可以用来求一个范围([1,n]?)的素数,思路是找的一个素数p就把1p,2p,3p….的数全部标记为合数,剩下的就都是素数辣~~(≧▽≦)/~
复杂度o(nloglogn)?(老师讲的我觉得可能是n^2???mengbi*1)
代码很简单(我就是不压行你打我啊)(没网,并不知道有没有bug)

bool v[MAXN];
int n;
int shai()
{
    for(int i=2;i<=n;i++)
    {
        if(!v[i])
        {
            for(int j=2;j*i<=n;j++)
            {
                v[j*i]=true;
            }
        }
    }
}

欧拉筛法

埃氏筛法在会把一个合数筛许多次…所以速度偏慢…在一些玄妙的数据范围下会爆炸…于是就有了一个合数只被筛一次的欧拉筛法…
欧拉筛法保证一个合数只被她最小的质因子筛掉…所以一个数只被筛一次…所以复杂度o(n)…
欧拉筛法不是有了一个质数(i)再去不停的枚举此质数的倍数(j),而是先确定一个倍数(i),再枚举最小的质因子p[j],筛掉合数i*p[j],如果这个质数p[j]已经不是i*p[j]的最小质因子,就break….
代码很简单(我就是不压行你打我啊)(我常数大你咬我啊)(没网,并不知道有没有bug)*2

bool v[MAXN];
int n;  
vector<int> p;
int shai()
{
    for(int i=2;i<=n;i++)
    {
        if(!v[i])
        {
            p.push_back(i);
        }
        for(int j=0;j<p.size()&&p[j]*i<=n;j++)
        {
            v[i*p[j]]=true;
            if(i%p[j]==0)
            {
                break;
            }
        }
    }
}

为啥i%p[j]==0的时候要break嘞?因为i是递增的,所以p里的素数大小也是递增的,所以i*p[j+1]这个数一定可以通过p[j]*某个i来筛掉(因为i里包含了p[j]),就没有必要通过p[j+1]筛了,所以跳出j的循环

gcd证明

这么简单的东西宽嫂才懒得写代码呢…
今天好像听了一个好懂点的gcd证明…
求证gcd(a,b)=gcd(b,a%b)
设t=gcd(a,b)
a=qt,b=pt;
则q与p互质(如果不互质的话t还可以乘以其最大公因数)
设k=q%p;
q=xp+k;
因为q与p互质,所以q与(xp+k)没有公因子,即p与k没有公因子(如果有就可以提出来然后使q与(xp+k)不互质),即p&&k互质(p与(q%p)互质),所以gcd(qt,pt)就转化为了gcd(pt,(q%p)t)(前面的系数如果互质就不影响结果)
嗯…大概就酱…不懂的话宽嫂也没办法╮(╯▽╰)╭

exgcd

这个玩意已经学了半年了呢…然而基本还是蒙蔽的[我退役吧.jpg]…
exgcd就是解线性同余方程(ax+by=gcd(a,b))的…
有ax+by=gcd(a,b) 给定a,b;求x,y;
设ax1+by1=gcd(a,b),那就xjb找一个x2,y2,使bx2+(a%b)y2=gcd(b,a%b);
因为上文说过gcd(a,b)==gcd(b,a%b),所以ax1+by1=bx2+(a%b)y2;
因为a%b==a-(a/b)*b,所以ax1+by1=bx2+(a-(a/b)*b)y2;
即ax1+by1=ay2+bx2-b*(a/b)y2
提出b: ax1+by1=ay2+b(x2-(a/b)y2)
不知道因为啥,x1=y2,y1=x2-(a/b)y2;
所以,通过y-=(a/b)*x的递归操作就可以写出exgcd了(/▽＼)

void exgcd (int a,int b,int &x,int &y)
{
    if(!b)
        x=1,y=0;
    else
        exgcd(b,a%b,d,y,x);
    y-=(a/b ) x ;
}

嗯…今天差不多就酱…明天再更吧….

By 懵逼的 Cansult