准备写的

数论,图论一点,TRICK(鬼知道会不会写)

由于懒得写 $\text{\text{}}$ 因此本文英语都会很奇怪

数论

比较基础的就放在前面了,下面可能不会再提到

唯一分解定理 $x=\Pi{p_i^{k_i}}$

公约数 $\gcd=\gcd(b,a\bmod b)$ (欧几里得求法)

$\large \gcd=\Pi{p_i^{\min(k1_i,k2_i)}}$ (唯一分解定理)

素数

只能被 $1$ 和自身除掉的数

个数大概是 $\frac{x}{\ln(x)}$

判断一个数是否为素数,可以用 $O(\sqrt{n})$ 的筛法,感觉是个人都会,故不贴代码

考虑小学筛,即为埃氏筛

1
2
3
for i in 1,n
for j in 2i,n step i
is_not_prime[i]=1;

复杂度分析 $O(n\log n)$

继续优化,每次判断 $\text{i}$ 是不是质数,可以做到$O(n\log\log n)$

然后考虑继续优化,考虑上面的过程,如果一个数有过多的素因子,那么效率大打折扣,那么如果我们枚举最大的因子不就可以了吗,于是有了欧拉筛

1
2
3
4
5
6
7
8
9
10
11
12
13
inline void getprime()
{
register int i,j;
for(i=2;i<=maxn;i++)
{
if(!vis[i]) p[++cnt]=i;
for(j=1;i*p[j]<=maxn&&j<=cnt;j++)
{
vis[i*p[j]]=1;
if(i%p[j]==0) break;
}
}
}

然后又有人嫌慢,比较这个要求 $[1,n]$ 的素数,对于单独的或者值域很大的情况没啥办法,引出 $\text{Miller_Rabin}$

考虑费马小定理 $a^{p-1}\equiv 1 \pmod p$

如果逆定理成立,我将绝杀吗可惜$p=561$ 炸了

于是我们又考虑这个式子

$x^2\equiv1\pmod p,x\equiv p-1\pmod {p}\text{ or } x\equiv 1\pmod p$

我们试着把$n-1$分解成 $2^k*p$ 的形式来探测。

由于卡迈尔克数不满足这种形式($p^e$),因此我们能够绝杀

但是随机数的时候也很难说哪些可以,不妨只取前几个素数(很玄学的是跑得很快)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int mr_rb(ll x,ll y)
{
//x--;
ll looker=x-1;
while(looker)
{
ll tmp=ksm(y,looker,x);
if(tmp!=1&&tmp!=x-1) return 0;
if((looker&1)||tmp!=1) return 1;
looker>>=1;
}
return 1;
}

int isprime(ll x)
{
if(x<2||x==46856248255981ll) return 0;
if(x==2||x==3||x==5||x==7||x==11||x==13||x==17||x==61||x==24251) return 1;
return mr_rb(x,2ll)&mr_rb(x,61ll);
//return mr_rb(x,2ll)&mr_rb(x,3ll)&mr_rb(x,5ll)&mr_rb(x,7ll)&mr_rb(x,11ll)&mr_rb(x,13ll)&mr_rb(x,17ll)&mr_rb(x,61ll)&mr_rb(x,24251ll);
}

复杂度近似为 $O(\log(n)^3)$

现在有人叫你给这种大合数分解因数,你又暴毙了

$\text{Pollar_Rho}$ 就是对付这种出题人的法宝

考虑生日悖论,如果能在某个东西的根号级别退出,那就太好了

如果 $(x,N)\neq1$ 就说明 $x$ 是个因子。

咕咕便是

exgcd&&裴蜀定理

对于以下式子

可以得到拓展欧几里得以及裴蜀定理

裴蜀定理是证明上面那个方程一定有解

我们尝试证明一下:

1.若其中一个为$0$,显然

2.否则就是更减相损,显然

然后你发现,更减相损?

这不就可以欧几里得吗?

然后就可以得到exgcd了

1
2
3
4
5
6
7
8
int exgcd(int a,int b,int &x,int &y)
{
if(b==0) {x=1;y=0; return a;}
int t=exgcd(b,a%b,x,y),tmp=x;
x=y;
y=tmp-(a/b)*y;
return t;
}