寒训day9 初等数论-白红宇

寒训day9 初等数论

阅读量：3954 次

发布时间：2019-05-24

本文共 5820 字，大约阅读时间需要 19 分钟。

初等数论四大定理

威尔逊定理

$\% p = 0$

其中，p是质数。

HDU 2973

题意

多组数据，给n，求 $S_n$

分析

化简成 $((p - 1)! + 1) / p$ 的形式，可以发现若 $3 k + 7$ 是质数，整块为1，否则为0。

代码

暴力了一波，果然TLE。最后稍微记忆化就过了。Leaderboard上面有打素数表的，时间减半。

#include
   
    #include
    
     using namespace std;int ans[1000006];is_prime(int x){
       if(x==1)return false;    int sq=sqrt(x);    for(int i=2;i<=sq;i++)    if(x%i==0)    {
           return false;    }    return true;}int main(){
       int t,n,cnt=1;    scanf("%d",&t);    while(t--)    {
           scanf("%d",&n);        if(n>=cnt)            for(;cnt<=n;cnt++)                ans[cnt]=ans[cnt-1]+is_prime(3*cnt+7);        printf("%d\n",ans[n]);    }}

欧拉定理

$a^{φ (n)}≡1\ (mod\ n)$

其中

φ (n)

是欧拉函数，表示小于n的正整数中与n互质的数的数目。

中国剩余定理（孙子定理）

费马小定理

$a^{p-1}≡1\pmod{p}$

其中，p是质数。其实就是欧拉定理的特例。

求除法取模逆元

$\frac{a}{b}=a*b^{p-2}\pmod{p}$

证明：

设\begin{cases}\frac{a}{b}=k1*p+y1\\a*x=k2*p+y2\\\frac{a}{b}-a*x=k*p+y\end{cases}且x*b=1\pmod{p}\\ \because a-a*x*b=k*p*b+y*b\\(a-a*x*b)=(k*p*b+y*b)\pmod{p}\\ 0=y*b又\because b=\not1\\ \therefore y=0又\because x*b=1, b^{p-1}≡1\pmod{p}\\ \therefore x=b^{p-2}可使\frac{a}{b}=a*x\pmod p成立.

~~丑陋证毕.~~

玄学判素数

伪素数

扩展

扩展欧几里得算法

反素数

定义：约数个数比所有小于x的正整数多，则称x为反素数。

约数数量与质因数的关系

约数数量 $n = 1 * (t 1 + 1) * (t 2 + 1) * (t 3 + 1) . . .$ 其中 $t 1, t 2 . . .$ 为各个质因数的数量。

反素数的质因数规律

反素数的所有质因子必然是从2开始的连续若干个质数，且 $x=2^{t1}*3^{t2}*5^{t3}...(t1≥r2≥t3...)$ ，因为反素数是保证约数个数为 $n$ 的这个数 $x$ 尽量小，用反证法易证。

#include
   
    #include
    
     #define un unsigned intusing namespace std;un per[10]={
   2,3,5,7,11,13,17,19,23,29},maxY=0,ans=2e9,n;void dfs(un Y,char dep,un num,char last){
   	if(Y>maxY)maxY=Y,ans=num;	if(Y==maxY)ans=min(ans,num);	for(char i=1;num<=n/per[dep]&&i<=last;i++)		dfs(Y*(i+1),dep+1,num*=per[dep],i);}int  main(){
   	char t;	scanf("%d",&t);	for(char i=1;i<=t;i++)	{
   		maxY=0,ans=2e9;		scanf("%u",&n);		dfs(1,0,1,33);		printf("Case #%d: %u\n",i,ans);	}}

当然，反素数是十分稀有的。换而言之，打表出奇迹。

#include
   
    #include
    
     #define un unsigned intusing namespace std;un a[]={
   1396755360,1102701600,735134400,698377680,551350800,367567200,294053760,245044800,183783600,147026880,122522400,110270160,73513440,61261200,43243200,36756720,32432400,21621600,17297280,14414400,10810800,8648640,7207200,6486480,4324320,3603600,2882880,2162160,1441440,1081080,720720,665280,554400,498960,332640,277200,221760,166320,110880,83160,55440,50400,45360,27720,25200,20160,15120,10080,7560,5040,2520,1680,1260,840,720,360,240,180,120,60,48,36,24,12,6,4,2,1};int  main(){
   	un t,n;	scanf("%u",&t);	for(un i=1;i<=t;i++)	{
   		scanf("%u",&n);		un j;		for(j=0;a[j]>n;j++);		printf("Case #%u: %u\n",i,a[j]);	}}

Locas定理

设 $n = a p + b, m = c p + d$ ,( $p$ is a prime number)

{n\choose m}={a\choose c}*{b\choose d}\ (mod\ p)

非严谨证明

二项式定理+费马小定理

由(1+x)^p=1+x=1+x^p\ (mod\ p)得

$1+x）^n=(1+x)^{ap}(1+x)^b=(1+x^p)^{a}(1+x)^b\ (mod\ p)$

则其中

x^m

的系数就是

{n\choose m}={a\choose c}*{b\choose d}\ (mod\ p)

费马大定理

当整数 $n > 2$ 时，关于 $x, y, z$ 的不定方程

x^n+y^n=z^n

没有正整数解。

Berlekamp–Massey算法

C++11的代码

#include 
   
    using namespace std;typedef long long ll;#define rep(i,a,n) for (int i=a;i
    
     =a;i--)#define pb push_back#define mp make_pair#define all(x) (x).begin(),(x).end()#define fi first#define se second#define SZ(x) ((ll)(x).size())typedef vector
     
       VI;typedef pair
      
        PII;const ll mod = 1000000007;ll powmod(ll a,ll b) {
   	ll res=1;	a%=mod;	assert(b>=0);	for(;b;b>>=1){
   	if(b&1) res=res*a%mod;	a=a*a%mod;	}	return res;}ll _,n;namespace linear_seq {
       const int N=10010;    ll res[N],base[N],_c[N],_md[N];    vector
       
         Md;    void mul(ll *a,ll *b,ll k) {
           rep(i,0,k+k) _c[i]=0;        rep(i,0,k)		if (a[i])		rep(j,0,k)		_c[i+j]=(_c[i+j]+a[i]*b[j])%mod;        for (ll i=k+k-1;i>=k;i--)		if (_c[i])            rep(j,0,SZ(Md))			_c[i-k+Md[j]]=(_c[i-k+Md[j]]-_c[i]*_md[Md[j]])%mod;        rep(i,0,k) a[i]=_c[i];		}    ll solve(ll n,VI a,VI b) {
       	ll ans=0,pnt=0;    	ll k=SZ(a);        assert(SZ(a)==SZ(b));        rep(i,0,k) _md[k-1-i]=-a[i];_md[k]=1;        Md.clear();        rep(i,0,k) if (_md[i]!=0) Md.push_back(i);        rep(i,0,k) res[i]=base[i]=0;        res[0]=1;        while ((1ll<
        
         <=n) pnt++; for (ll p=pnt;p>=0;p--) { mul(res,res,k); if ((n>>p)&1) { for (ll i=k-1;i>=0;i--) res[i+1]=res[i];res[0]=0; rep(j,0,SZ(Md)) res[Md[j]]=(res[Md[j]]-res[k]*_md[Md[j]])%mod; } } rep(i,0,k) ans=(ans+res[i]*b[i])%mod; if(ans<0) ans+=mod; return ans; } VI BM(VI s) { VI C(1,1),B(1,1); ll L=0,m=1,b=1; rep(n,0,SZ(s)) { ll d=0; rep(i,0,L+1) d=(d+(ll)C[i]*s[n-i])%mod; if (d==0) ++m; else if (2*L<=n) { VI T=C; ll c=mod-d*powmod(b,mod-2)%mod; while (SZ(C)