一个关于逆元的小技巧
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'}的质因子。
具体程序如下
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
<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然后好长时间才查出来 真可怕
就放个板子 具体原理上面证完了。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
<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)