簡單數論知識梳理(省選複習)

(noip數論算法彙總)

①擴充歐幾裡得

int ex_gcd(int a,int b,int &x,int &y)
{
	if(!b)
	{
		x=1,y=0;
		return a;
	}
	int g=ex_gcd(b,a%b,x,y);
	int t=x;x=y,y=t-a/b*y;
	return g;
}
           

應用及要點：

one :   求形如ax+by=gcd(a,b)的一組解(x,y)  （有解情況當且僅當ab互質）

    要注意的是,已知一組解(x0,y0),則其他所有解都可以表示成(x0+k*b,y0-k*a)

    想像成直線就可以了解了

two:    求逆元，ax≡1 mod(p) 可以轉化為 ax-py=1

另：

輾轉相除和輾轉相減法兩個定理：

輾轉相減法：gcd(a,b)=gcd(a-b,b)

輾轉相除法：gcd(a,b)=gcd(a%b,b)

②分解質因數

O(sqrt(n))太無腦了無視掉

O(n)預處理和O(log(a))分解:

線性篩法預處理 dy[i] 表示i的最小質因子在prime數組中的編号

分解時每次除以最小質因子即可做到log的分解質因數

代碼:

void init()
{
	for(int i=2;i<=n;i++)
	{
		if(!vis[i])prime[++cnt]=i;
		for(int j=1;j<=cnt;j++)
		{
			long long tmp=prime[j]*i;
			if(tmp>=N)break;
			vis[tmp]=1,dy[tmp]=j;
			if(tmp%prime[j]==0)break;
		}
	}
}
int num[N];
void work(int x)
{
	while(x!=1)
	{
		num[dy[x]]++;
		x/=prime[dy[x]];
	}
}
           

③逆元：

常用的有三種,擴充歐幾裡得上面提到了,下面隻寫費馬小定理和線性遞推求逆元

費馬小定理：a^(p-2)是a在膜p意義下的逆元，即a^(p-1)%p=1

ll qm(ll a,ll b)
{
	ll ret=0,t=a;
	while(b)
	{
		if(b&1)ret=ret*t%mod;
		t=t*t%mod;b>>=1;
	}return ret;
}
ll inv(ll x){return qm(x,mod-2); }
           

線性遞推逆元:  inv[1]=1,inv[i]=inv[p%i]*(p-p/i)%p

讓我來認真的證明一次上式.....(noip前真的是差到連這玩意都不會證.......)

設 t=p/i,k=p%i

則 p=t*i+k

即 (t*i+k)≡0(mod p)

=>  -t*i≡k(mod p)

兩邊同時除以i*k

=> -t*inv[k]≡inv[i](mod p)

故inv[i]=-t*inv[k](mod p)

轉成正數：inv[i]=(-t+p)*inv[k](mod p)

是以 inv[i]=(p-p/i)*inv[p%i](mod p)

可以愉快的線性推逆元啦23333

int inv[N];
void init()
{
	inv[1]=1;
	for(int i=2;i<mod;i++)
		inv[i]=(mod-mod/i)*inv[mod%i]%mod;
}
           

④歐拉函數：

 線性篩求歐拉函數前面一篇部落格裡已經提到過，在此不提

歐拉函數的意義:

phi[n]=小于n的數中與n互質的數的個數

定義式：

phi[n]=n*(1-1/p1)*(1-1/p2)*(1-1/p3)....(1-1/pk)

這很簡單就不放代碼了。

應用：

one ：上一個求逆元中還有一種方法沒有說到就是歐拉函數。

   有歐拉定理：a^φ(n)  ≡ 1 mod n 

two ： 按定義，求小于n且與n互質的數的個數(2333)

three：求n以内與n互質的數的和

    有公式：sum(n)=phi(n)*n/2; (sum(n)為小于n的所有與n互質的數的和)

⑤一些實用的定理：

約定：

唯一分解式形為n=p1^a1*p2^a2*p3^a3*…*pk^ak

約數個數定理： n的約數個數=(a1+1)*(a2+1)*(a3+1)....(ak+1)

約數和定理：     n的約數和=(p1^0+p1^1+p1^2...p1^a1)*(p2^0+p2^1+p2^2....p2^a2)...(pk^0+pk^1...pk^ak)

基礎的數論知識差不多就是這些了，後面幾篇部落格會對幾個重要的數論知識點進行詳解或較多例題複習

⑥等比數列求和的分治算法：

定理：

對于Sn=a^1+a^2+...+a^n

當n==0時Sn=1;n==1時Sn=a

當n為偶數時：

Sn=S(n/2)*(a^(n/2)+1)

當n為奇數時：

Sn=S(n/2)*(a^(n/2+1)+1)+(a^(n/2)+1)