一个关于逆元的小技巧

ans = \frac{a}{b}\bmod m = a\bmod \left( {mb} \right)/b

那么下面是证明

\begin{array}{l}\frac{a}{b} = km + x{\rm{ }}\left( {x < m} \right)\\a = kbm + bx\\a\bmod bm = \left( {kbm\bmod bm} \right) + \left( {bx\bmod bm} \right)\\a\bmod bm = bx\\\frac{{a\bmod bm}}{b} = x\\\frac{a}{b}\bmod m = \left( {km\bmod m} \right) + \left( {x\bmod m} \right)\\\frac{a}{b}\bmod m = x\end{array}

为什么我觉得没多大用处……


唯一分解定理

将一个非素数N 唯一分解成有限个素数的乘积

N = \prod\limits_{i = 1}^n {p_i^{{a_{_i}}}}

快速分解:每次只枚举不大于\sqrt {N'}的所有质数(N'\frac{N}{{\prod\limits_{i = 1}^\delta {p_i^{{a_i}}} }},其中\delta是目前枚举到的质数个数 )

可以证明N'只有最多一个超过\sqrt {N'}的质因子。

具体程序如下

<span style="color: #000000;">#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<iterator>
using namespace std;

int n,n1,upat;

int main()
{
	scanf("%d",&n);
	upat=sqrt(n)+1;
	n1=n;
	for (int i=2;i<=upat;i++)
	{
		while (n1%i==0)
		{
			printf("%d ",i);
			n1=n1/i;
			upat=sqrt(n1)+1;
		}
	}
	if (n1!=0) printf("%d\n",n1);
	return 0;
}</span>

 

今天是1月7日,昨天湖南师附集训 宾馆网速40kb/s 本来想传上费马小定理和二次探测定理的证明 结果编辑页面开了2h无果……

Day2 20:35上传一下

上传失败了,Day4 00:02再上传一下

\begin{array}{l}a^{p-1}\equiv 1\,\,\left( \text{mod}\,p \right) \,\,\left( p\text{为素数,}p\nmid a\text{不成立且}a>0 \right)\\\text{记}A=\left\{ a,2a,3a,\cdots ,\left( p-1 \right) a \right\} ,B=\left\{ 1,2,3\cdots ,p-1 \right\}\\A=B\,\,\left( \text{mod}\,p \right) \\ \text{对于}\forall a\in A,\text{存在唯一}b\in B\text{且}a\equiv b\,\,\left( \text{mod}\,p \right) \\\text{如果}a_1,a_2\in A,a_1\equiv a_2\,\,\left( \text{mod}\,p \right) \,\,,\,\,\text{则上式不成立}\\\text{记}a_1=i\times a,a_2=j\times a\\\text{则有}i\times a\,\,\equiv \,\,j\times a\,\,\left( \text{mod}\,p \right) \,\,\left( 0<i,j<p \right) \\\therefore \left( i-j \right) \times a\equiv 0\,\,\left( \text{mod}\,p \right) \\\therefore \left( i-j \right) \equiv 0\,\,\left( \text{mod}\,p \right) \\\therefore i=j\\\because A=B\,\,\left( \text{mod}\,p \right) \\a\times 2a\times 3a\times \cdots \times \left( p-1 \right) a\equiv 1\times 2\times \cdots \times \left( p-1 \right) \,\,\left( \text{mod}\,p \right) \\a^{\left( p-1 \right)}\times \left( p-1 \right) !\equiv \left( p-1 \right) !\,\,\left( \text{mod}\,p \right) \\a^{p-1}\equiv 1\,\,\left( \text{mod}\,p \right) \end{array}

下面是二次探测的证明……? 主要是用在Miller-Rabin上吧……

\begin{array}{l}x^2\equiv 1\,\,\left( \text{mod}\,p \right) \,\,\left( p\text{为素数,}x\in \mathbb{Z} \right)\\x^2-1\equiv 0\,\,\left( \text{mod}\,p \right)\\\left( x+1 \right) \left( x-1 \right) \equiv 0\,\,\left( \text{mod}\,p \right)\\\left( x-1 \right) \equiv 0\text{或}\left( x+1 \right) \equiv 0\,\,\left( \text{mod}\,p \right)\\p=2\text{显然成立}\\p>2\text{时,}\\\left( x+1 \right) \equiv 0\,\,\text{或}\left( x-1 \right) \equiv 0\,\,\left( \text{mod}\,p \right)\\x\equiv \pm 1\,\,\left( \text{mod}\,p \right) \end{array}

接下来是Miller-Rabin,写的时候用费马小定理居然没有判gcd然后好长时间才查出来     真可怕

就放个板子 具体原理上面证完了。

<span style="color: #000000;">#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<iterator>
#include<ctime>
using namespace std;

long long prime,opt;

inline long long fastpow(long long an,long long p)
{
    long long res=1;
    for (;p;p>>=1,an=an*an%prime) if (p&1) res=an*res%prime;
    return res;
}
inline long long lowbit(long long xx) { return xx&(-xx); }
inline void readx(long long& x)
{
    x=0; long long k=1; register char ch=0;
    while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    x*=k;
}

inline long long gcd(long long a,long long b)
{
    if (b==0) return a;
    else return gcd(b,a%b); 
}

inline bool MillerRabin()
{
    register long long prx=prime-1,u=prime-1,lim=0;
    register long long pox,rec,a;
    
    lim=lowbit(u); u=u/lim;
    for (register int i=1;i<=10;i++)
    {
        a=rand()%prime; lim=lowbit(prx);
        while (!a) a=rand()%prime;
        pox=fastpow(a,u);
        for (;lim;lim>>=1)
        {
            rec=(pox*pox)%prime;
            if (rec==1 && pox!=prime-1 && pox!=1) return false;
            pox=rec;
        }
        if (pox!=1) return false;
    }
    return true;
}

int main()
{
    srand(time(0)); readx(opt);
    for (int i=1;i<=opt;i++)
    {
        readx(prime); if (prime==1) prime=4;
        if (prime==2 || MillerRabin()) printf("Yes\n");
        else printf("No\n");
    } 
    return 0;
}</span>

不是很难,也就几行.


2018-3-22 update

遇到一个有趣的式子……

F\left( a+b \right) =F\left( a+1 \right) \times F\left( b \right) +F\left( a \right) \times F\left( b-1 \right)

还有就是

\begin{array}{l} \text{gcd}\left( F\left( a \right) ,F\left( b \right) \right) \\ =\,\,\text{gcd}\left( F\left( a-b+b \right) ,F\left( b \right) \right) \\ =\,\,\text{gcd}\left( F\left( a-b \right) \times F\left( b-1 \right) ,F\left( b \right) \right) \end{array}

然后可以化为

\text{gcd}\left( F\left( a-b \right) ,F\left( b \right) \right) \ =\ F\left( \text{gcd}\left( a,b \right) \right)


\begin{array}{l} \phi \left( x \right) =\left( a_1-1 \right) a_{1}^{p_1-1}\cdot \left( a_2-1 \right) a_{2}^{p_2-1}\cdots \left( a_n-1 \right) a_{n}^{p_n-1} \\ \text{原理:\ 当}x=p^n\text{时\ ,\ }\phi \left( x \right) =x-x/p=p^n-p^{n-1}=\left( p-1 \right) p^{n-1}\ \text{而且}\phi \left( x \right) \text{是积性函数} \end{array}


线性筛的证明

\gcd(n,m)=1 \Rightarrow \gcd(n+m,m)=1

n,m 不互质时,

b=\gcd(n,m) \;\; (b \ne 1) 则有

\begin{cases} n+m=k_2b\\ m=k_1b \end{cases} \;\;\;(k_1,k_2 \in \mathbb{Z})

\Rightarrow k_1b+n=k_2b

\Rightarrow n=(k_2-k_1)b

\Rightarrow \gcd(n,m)=b

这与\gcd(n,m)=1矛盾。

所以我们有了\varphi(p \times i)=p \times \varphi(i)

分类: 数论