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

唯一分解定理

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

埃氏筛法

筛法用于求一堆素数;
筛法是基于一个显而易见的道理:素数没有比她小的因子,这也是朴素求素数算法的基础(枚举2~sqrt(n))朴素算法是有一个数,然后判断她是否是素数,求一个范围的素数显然爆炸,那么推广一下,如何求一堆素数嘞?筛法啊QAQ
埃氏筛法可以用来求一个范围($[1,n]$?)的素数,思路是找的一个素数p就把$1\cdot p,2\cdot p,3\cdot p \cdots$的数全部标记为合数,剩下的就都是素数辣
复杂度$\mathrm O(n \lg^2 n)$?(老师讲的我觉得可能是$n \sqrt n$???$mengbi \times 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;
}

欧拉筛法

埃氏筛法在会把一个合数筛许多次…所以速度偏慢…在一些玄妙的数据范围下会爆炸…于是就有了一个合数只被筛一次的欧拉筛法…
欧拉筛法保证一个合数只被她最小的质因子筛掉…所以一个数只被筛一次…所以复杂度$\mathrm O(n)$…
欧拉筛法不是有了一个质数(i)再去不停的枚举此质数的倍数(j),而是先确定一个倍数(i),再枚举最小的质因子$p[j]$,筛掉合数$i \cdot p[j]$,如果这个质数$p[j]$已经不是$i \cdot p[j]$的最小质因子, 就break….
代码很简单(我就是不压行你打我啊)(我常数大你咬我啊)(没网,并不知道有没有bug) $\times 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 \equiv 0 \pmod {p[j]}$的时候要break嘞? 因为i是递增的, 所以$p$里的素数大小也是递增的,所以$i \cdot p[j+1]$这个数一定可以通过 $p[j] \cdot some\,i$ 来筛掉(因为i里包含了p[j]),就没有必要通过$p[j + 1]$筛了,所以跳出j的循环

gcd证明

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

exgcd

这个玩意已经学了半年了呢…然而基本还是蒙蔽的[我退役吧.jpg]…
exgcd就是解线性同余方程$(ax + by = \gcd(a,\,\, b))​$的…
有$ax + by = \gcd(a,\,\, b)$ 给定$a, b$求$x, y$
设$ax_1 + by_1 = \gcd(a,\,\, b)$,那就xjb找一个$x_2,y_2$,使$bx_2 + (a\,\, mod\,\, b) \cdot y_2 = \gcd(b,\,\, a\,\, mod\,\, b)$
因为上文说过$\gcd(a,\,\,b) = gcd(b,\,\, a \,\,mod\,\, b)$,所以$ax_1 + by_1 = bx_2 + (a\,\, mod\,\, b) \cdot y_2$
因为$a \,\, mod\,\, b = a - (a / b) \cdot b$,所以$ax_1 + by_1 = bx_2 + (a - (a / b) \cdot b) \cdot y_2$
即$ax_1 + by_1 = ay_2 + bx_2 - b \cdot (a / b) \cdot y_2$
提出$b$: $ax_1 + by_1 = ay_2 + b \cdot (x_2 - (a / b) \cdot y2)$
不知道因为啥,$x_1 = y_2, y_1 = x_2 - (a / b) * y_2$
所以,通过$y -= (a / b) \cdot 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;
}

update: 注意如果求出$x, y​$为负, 而题目要求为正的话, 可以通过

LL solve(LL a, LL b)
{
    LL x, y;
    LL gcd = exgcd(a, b, x, y);
    LL tb = b / gcd;
    while (x < 0)
        x += tb;
    return x;
}

来求最小正整数解

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

2017-07-31 19:59:00

By 懵逼的 Cansult