(2)a|b且a|c等价于对于自由的平头x,若是存在一个整数q

原博客:
http://blog.csdn[.net](http://lib.csdn.net/base/dotnet)/ray58750034/archive/2006/03/27/640074.aspx

【SinGuLaRiTy-1004】 Copyright (c) SinGuLaRiTy 2017 . All Rights
Reserved.

【SinGuLaRiTy-1004】 Copyright (c) SinGuLaRiTy 2017 . All Rights
Reserved.

欧拉函数 :
欧拉函数是数论中很关键的一个函数,欧拉函数是指:对于叁个正整数 n ,小于
n 且和 n 互质的正整数(包涵 1)的个数,记作 φ(n) 。

整除

整除

一齐余数集合:
概念小于 n 且和 n 互质的数构成的聚合为 Zn ,称呼那个集合为 n
的一点一滴余数集合。 明显 |Zn| =φ(n) 。

基本概念

设a,b为整数,且a不为0,假如存在贰个整数q,使得a*q=b,则b能被a整除,记为a|b,且称b是a的倍数,a是b的因子。

基本概念

设a,b为整数,且a不为0,要是存在二个整数q,使得a*q=b,则b能被a整除,记为a|b,且称b是a的倍数,a是b的因子。

至于性质:
对此素数 p ,φ(p) = p -1 。
对于几个不等素数 p, q ,它们的乘积 n = p * q 满足 φ(n) = (p -1) * (q
-1)  。
那是因为 Zn = {1, 2, 3,  … , n – 1} – {p,
2p, … , (q – 1) * p} – {q, 2q, … , (p – 1) * q} , 则 φ(n) = (n –
1) – (q – 1) – (p – 1) = (p -1) * (q -1)  =φ(p) * φ(q) 。

性质

(1)如果a|b且b|c,则a|c ;
(2)a|b且a|c等价于对于自由的整数x,y,有a|(bx+cy) ;
(3)设m不为0,则a|b等价于ma|mb ;
(4)设整数x,y满足下式:ax+by=1,且a|n,b|n,那么(ab)|n ;
(5)若b=q*d+c,那么d|b的充要条件是d|c ;

<补充拓展>

(1)若2能整除a的最倒数一位,则2|a

表明:若原数减去协调的最末尾,获得的数一定能被10整除,即一定能被2整除,又因为最末尾也能被2整除,则原数一定能被2整除
(2)若4能整除a的末两位,则4|a

表明:原理与(1)的貌似。若原数减去协调的末两位倒数,得到的数一定能被100整除,即一定能被4整除,又因为末两位也能被4整除,则原数一定能被4整除
(3)若8能整除a的末多少人,则8|a

证明:原理与(1)(2)相似。
(4)若3能整除a的各位数字之和,则3|a

表明:设随意八个数S=a\10^0+b*10^1+c*10^2+d*10^3+……*

*                                 
=(a+b+c+d+……)+9b+99c+999d+9999e+……*

*         
由于3|(a+b+c+d+……),3|(9b+99c+999d+9999e+……),则3|S*
(5)若9能整除a的各位数字之和,则9|a

证明:原理与(4)相同。
(6)若11能整除a的偶数位数字之和与奇数位数字之和的差,则11|a

申明:设随意三个数S=a\10^0+b*10^1+c*10^2+d*10^3+……*

*                                 
=(a-b+c-d+……)+11b+99c+1001d+……*

*         
 由于11|(a-b+c-d+……),11|(11b+99c+1001d+……),则11|S*
(7)能被柒 、1壹 、13整除的数的特性是:这几个数的末多少人与末三个人从前的数字所构成数之差能被⑦ 、1壹 、13整除。

证明:原理与(6)相同。

性质

(1)如果a|b且b|c,则a|c ;
(2)a|b且a|c等价于对于随意的平头x,y,有a|(bx+cy) ;
(3)设m不为0,则a|b等价于ma|mb ;
(4)设整数x,y满意下式:ax+by=1,且a|n,b|n,那么(ab)|n ;
(5)若b=q*d+c,那么d|b的充要条件是d|c ;

<补充拓展>

(1)若2能整除a的最倒数一位,则2|a

证实:若原数减去团结的最末尾,获得的数一定能被10整除,即一定能被2整除,又因为最末尾也能被2整除,则原数一定能被2整除
(2)若4能整除a的末两位,则4|a

申明:原理与(1)的一般。若原数减去团结的末两位倒数,获得的数一定能被100整除,即一定能被4整除,又因为末两位也能被4整除,则原数一定能被4整除
(3)若8能整除a的末叁人,则8|a

证明:原理与(1)(2)相似。
(4)若3能整除a的诸位数字之和,则3|a

注脚:设随意3个数S=a\10^0+b*10^1+c*10^2+d*10^3+……*

*                                 
=(a+b+c+d+……)+9b+99c+999d+9999e+……*

*         
由于3|(a+b+c+d+……),3|(9b+99c+999d+9999e+……),则3|S*
(5)若9能整除a的各位数字之和,则9|a

证明:原理与(4)相同。
(6)若11能整除a的偶数位数字之和与奇数位数字之和的差,则11|a

注明:设随意一个数S=a\10^0+b*10^1+c*10^2+d*10^3+……*

*                                 
=(a-b+c-d+……)+11b+99c+1001d+……*

*         
 由于11|(a-b+c-d+……),11|(11b+99c+1001d+……),则11|S*
(7)能被七 、1一 、13整除的数的特征是:这几个数的末三个人与末4个人在此以前的数字所构成数之差能被柒 、1壹 、13整除。

证明:原理与(6)相同。

欧拉定理 :
对此互质的正整数 a 和 n ,有 aφ(n)  ≡ 1 mod n  。

GCD & LCM:

*相似的,设a1,a2,a3,……ak是k个正整数,如若存在四个正整数d,使得d|a1,d|a2,……d|ak,那么d则为a1,a2,……ak的公约数,在那之中最大的号称最大公约数,即为gcd(a1,a2,……,ak),分明它是存在的,至少为1。当gcd=1时,称那n个数是互质的或既约的。公约数一定是最大公约数的约数。

*一般的,设a1,a2,a3,……ak是k个正整数,要是存在2个正整数d,使得a1|d,a2|d,a3|d,……ak|d,那么d则为a1,a2,……ak的倍数,当中非常的小的称呼最小公倍数数,记为lcm。

GCD & LCM:

*貌似的,设a1,a2,a3,……ak是k个正整数,假如存在三个正整数d,使得d|a1,d|a2,……d|ak,那么d则为a1,a2,……ak的公约数,当中最大的称之为最大公约数,即为gcd(a1,a2,……,ak),显明它是存在的,至少为1。当gcd=1时,称那n个数是互质的或既约的。公约数一定是最大公约数的约数。

*相似的,设a1,a2,a3,……ak是k个正整数,如若存在1个正整数d,使得a1|d,a2|d,a3|d,……ak|d,那么d则为a1,a2,……ak的倍数,个中非常小的名叫最小公倍数数,记为lcm。

证明:
( 1 ) 令 Zn = {x1, x2, …, xφ(n)} , S = {a * x1 mod n, a * x2 mod n, … , a * xφ(n) mod n} ,
        则 Zn = S 。
        ① 因为 a 与 n 互质, xi
(1 ≤ i ≤ φ(n)) 与 n 互质, 所以 a * xi  与
n 互质,所以 a * xi 
mod n ∈ Zn 。
        ② 若 i ≠ j , 那么 xi
xj,且由 a, n互质可得 a * xi
mod n ≠ a * xj mod n (消去律)。

<欧几里得算法(辗转相除法)>

gcd(a,b)=gcd(b,a%b)
性质:若a,b为偶数,则gcd(a,b)=2*gcd(a/2,b/2);若a偶b奇,则gcd(a,b)=gcd(a/2,b)。

<达成代码>

long long gcd(long long x,long long y){  
        if(x>y)return gcd(y,x);  
        if(x==0)return y;  
        return gcd(y%x,x);  
}  

由于有lcm(a,b)*gcd(a,b)=a*b,则lcm(a,b)=a*b/gcd(a,b)。

<欧几里得算法(辗转相除法)>

gcd(a,b)=gcd(b,a%b)
性质:若a,b为偶数,则gcd(a,b)=2*gcd(a/2,b/2);若a偶b奇,则gcd(a,b)=gcd(a/2,b)。

<达成代码>

long long gcd(long long x,long long y){  
        if(x>y)return gcd(y,x);  
        if(x==0)return y;  
        return gcd(y%x,x);  
}  

由于有lcm(a,b)*gcd(a,b)=a*b,则lcm(a,b)=a*b/gcd(a,b)。

( 2 )     aφ(n) * x1
* x2
*… * xφ(n) mod n
      ≡ (a
* x1) * (a *
x2) * … * (a
* xφ(n)) mod n
      ≡ (a * x1
mod
n) * (a
* x2 mod n) * … * (a
* xφ(n) mod n) mod n
      ≡  x1
* x2 * … * xφ(n) mod n
      比较等式的左右两岸,因为 xi  (1
≤ i ≤ φ(n)) 与 n 互质,所以 aφ(n)  ≡  1 mod n (消去律)。
注:
消去律:如果 gcd(c,p) = 1 ,则 ac ≡ bc mod p ⇒ a ≡ b mod p 。

勾股数:

对此正整数x,y,z,尽管满意等式:x^2+y^2=z^2,则称这组整数(x,y,z)为勾股数。换句话说,凡是足以整合直角三角形的平头即称为勾股数。
x,y,z两两互质的勾股数称为基本勾股数,如(3,4,5),(5,12,13),别的勾股数称为派生勾股数。基本勾股数乘以一个周全则足以获取派生勾股数。
基本勾股数的奇偶性?
肯定是二奇一偶,且最大的为奇数。
富有的基本勾股数都可以写成如下格局:
x=2mn,y=m^2-n^2,z=m^2+n^2 (m>n)
透过它能够枚举基本勾股数。

勾股数:

对周振天整数x,y,z,如果满意等式:x^2+y^2=z^2,则称那组整数(x,y,z)为勾股数。换句话说,凡是能够组合直角三角形的平头即称为勾股数。
x,y,z两两互质的勾股数称为基本勾股数,如(3,4,5),(5,12,13),别的勾股数称为派生勾股数。基本勾股数乘以八个全面则足以博得派生勾股数。
基本勾股数的奇偶性?
自然是二奇一偶,且最大的为奇数。
持有的基本勾股数都足以写成如下情势:
x=2mn,y=m^2-n^2,z=m^2+n^2 (m>n)
透过它可以枚举基本勾股数。

费马定理 :
若正整数 a 与素数 p 互质,则有 ap\ -\ 1 ≡ 1 mod p 。
表明这些定律格外简单,由于 φ(p) = p
-1,代入欧拉定理即可验证。

<勾股数完全公式>

a=m,b=(m^2/k-k) / 2,c=(m^2/k+k)/2 其中m≥3
⒈ 当m分明为随意二个≥3的奇数时,k={1,m^2的享有小于m的因子}
⒉ 当m明确为随机一个 ≥4的偶数时,k={m^2 / 2的有着小于m的偶数因子}
通过此公式能够求出全数的基本勾股数和派生勾股数,并能够求出给定a
时勾股数的组数。

<勾股数完全公式>

a=m,b=(m^2/k-k) / 2,c=(m^2/k+k)/2 其中m≥3
⒈ 当m鲜明为随意八个≥3的奇数时,k={1,m^2的持有小于m的因子}
⒉ 当m明确为私自三个 ≥4的偶数时,k={m^2 / 2的兼具小于m的偶数因子}
因此此公式能够求出全体的基本勾股数和派生勾股数,并能够求出给定a
时勾股数的组数。

参照来源:
http://zhidao.baidu.com/question/15882452.html?si=2

<求勾股数的组数>

当a给定时,不一致勾股数组a,b,c的组数N等于①式中k的可取值个数

取奇数a=P1^M1×P2^M2×……×Pr^Mr,个中k={1,a^2的具备小于a的因子},则k的可取值个数:
N=[(2*M1+1)×(2M2+1)×……×(2Mr+1)-1]/2

取偶数a=2^M0×P1^M1×P2^M2×……×Pr^Mr,当中k={a^2/2的拥有小于a的偶数因子},则k的可取值个数:
N=[(2M0-1)×(2M1+1)×(2M2+1)×……×(2Mr+1)-1]/2
里头,P1,P2,……,Pr为有差异的奇素数,M0,M1,……,Mr为幂指数。

<求勾股数的组数>

当a给定时,差别勾股数组a,b,c的组数N等于①式中k的可取值个数

取奇数a=P1^M1×P2^M2×……×Pr^Mr,在那之中k={1,a^2的富有小于a的因子},则k的可取值个数:
N=[(2*M1+1)×(2M2+1)×……×(2Mr+1)-1]/2

取偶数a=2^M0×P1^M1×P2^M2×……×Pr^Mr,个中k={a^2/2的兼具小于a的偶数因子},则k的可取值个数:
N=[(2M0-1)×(2M1+1)×(2M2+1)×……×(2Mr+1)-1]/2
内部,P1,P2,……,Pr为不完全一样的奇素数,M0,M1,……,Mr为幂指数。

》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》

模运算:

模运算:

增加补充:欧拉函数公式

<小平头的幂取模>

#define LL long long int
LL power(int a,int b,int p) //a^b%p
{
   int t=a,res=1;
   while(b)
   {
   if(b&1)
         res=res*t%p;
         t=t*t%p;
         b>>=1;
     }
}

<小平头的幂取模>

#define LL long long int
LL power(int a,int b,int p) //a^b%p
{
   int t=a,res=1;
   while(b)
   {
   if(b&1)
         res=res*t%p;
         t=t*t%p;
         b>>=1;
     }
}

( 1 ) pk 的欧拉函数

对此给定的一个素数 p , φ(p) = p -1。则对此正整数 n = pk

φ(n) = pk - pk -1

证明:
 小于 pk 的正整数个数为 pk - 1个,其中
 和 pk 不互质的正整数有{p * 1,p * 2,...,p * (pk - 1-1)} 共计 pk - 1 - 1 个
 所以 φ(n) = pk - 1 - (pk - 1 - 1) = pk - pk - 1 。

<大整数的模乘法>

#define LL long long int
LL mul(LL a, LL b, LL p)  //a*b%p
{  
     LL rn=0, i;  
     for(i=1; i<=b; i<<=1,a=(a<<1)%p)
         if(b&i) 
             rn=(rn+a)%p;  
     return rn;  
}

<大整数的模乘法>

#define LL long long int
LL mul(LL a, LL b, LL p)  //a*b%p
{  
     LL rn=0, i;  
     for(i=1; i<=b; i<<=1,a=(a<<1)%p)
         if(b&i) 
             rn=(rn+a)%p;  
     return rn;  
}

( 2 ) p * q 的欧拉函数

假设 p, q是七个互质的正整数,则 p * q 的欧拉函数为

φ(p * q) = φ(p) * φ(q) , gcd(p, q) = 1 。

证明:
 令 n = p * q , gcd(p,q) = 1
 根据中国余数定理,有
 Zn 和 Zp × Zq 之间存在一一映射
(我的想法是: a ∈ Zp , b ∈ Zq ⇔ b * p + a * q ∈ Zn 。)
 所以 n 的完全余数集合的元素个数等于集合 Zp × Zq 的元素个数。
 而后者的元素个数为 φ(p) * φ(q) ,所以有
 φ(p * q) = φ(p) * φ(q) 。

<大整数的幂取模>

#define LL long long int
LL ksm(LL a, LL b, LL p)  
{  
     LL rn=1;  
     for(; b; a=mul(a,a,p),b>>=1)  
         if(b&1) 
             rn=mul(rn,a,p);  
     return rn;  
} 

<大整数的幂取模>

#define LL long long int
LL ksm(LL a, LL b, LL p)  
{  
     LL rn=1;  
     for(; b; a=mul(a,a,p),b>>=1)  
         if(b&1) 
             rn=mul(rn,a,p);  
     return rn;  
} 

( 3 ) 任意正整数的欧拉函数

随便贰个整数 n 都能够象征为其素因子的乘积为:

      I
 n = ∏  piki (I 为 n 的素因子的个数)
     i=1

听他们讲前面七个结论,很不难得出它的欧拉函数为:

         I                      I
 Φ(n) = ∏  piki -1(pi -1) = n ∏ (1 - 1 / pi)
        i=1                    i=1

对于任意 n > 2,2 | Φ(n) ,因为必存在 
pi -1是偶数。

程序代码可参见:http://blog.csdn[.NET](http://lib.csdn.net/base/dotnet)/Rappy/archive/2007/08/16/1747489.aspx

 

 

素数:

对于三个正整数n,固然它的约数唯有1和n,则称n为质数。质数不带有1。
(1)素数有无穷多少个。
(2)不当先n的素数个数可粗略估量为n/ln(n)
(3)任何大于1的非素数n,那么在[1,sqrt(n)]区间内至少存在二个素数。

素数:

对此一个正整数n,要是它的约数只有1和n,则称n为质数。质数不带有1。
(1)素数有无穷多少个。
(2)不超过n的素数个数可归纳测度为n/ln(n)
(3)任何大于1的非素数n,那么在[1,sqrt(n)]间隔内至少存在二个素数。

<整数唯一分解定理>

随机三个高于1的平头n,均能够代表为多少个素数的乘积,且这么些格局是唯一的。
n=p1^m1*p2^m2*……pk^mk
里面,p1,p2,……pk 为n的质因子。

<整数唯一分解定理>

随便3个过量1的平头n,均能够象征为多少个素数的乘积,且那一个方式是绝无仅有的。
n=p1^m1*p2^m2*……pk^mk
710官方网站,个中,p1,p2,……pk 为n的质因子。

<不难的素数判断>

bool prime(int num)
{
    for(int i=2;i*i<=num;i++)
    {
        if(num%i==0)
            return 0;
     return 1;
    }
}

*频率更高的【Miller罗布in素数判定法】

<简单的素数判断>

bool prime(int num)
{
    for(int i=2;i*i<=num;i++)
    {
        if(num%i==0)
            return 0;
     return 1;
    }
}

*频率更高的【Miller罗布in素数判定法】

<线性时间筛素数>

//法一
const in MAXN=1000000+10;
const int MAXP=70000;
int vis[MAXN];
int prime[MAXP]
void sieve(int n)
{
 int m=(int)sqrt(n+0.5);
memset(vis,0,sizeof(vis));
for(int i=2;i<=m;i++)
if(!vis[i])
for(int j=i*i;j<=n;j+=i)
vis[j]=1;
}

//法二
int prime[MAXP];
bool flag[MAXN];
int j=0;
for(int i=2;i<=n;i++)
{
   if(flag[i]==0)
    prime[j++]=i;
    for(int k=0;k<j;k++)
    {
       if(prime[k]*i>n)break;
       flag[prime[k]*i]=1;
       if(i%prime[k]==0)break;
    }
}

<线性时间筛素数>

//法一
const in MAXN=1000000+10;
const int MAXP=70000;
int vis[MAXN];
int prime[MAXP]
void sieve(int n)
{
 int m=(int)sqrt(n+0.5);
memset(vis,0,sizeof(vis));
for(int i=2;i<=m;i++)
if(!vis[i])
for(int j=i*i;j<=n;j+=i)
vis[j]=1;
}

//法二
int prime[MAXP];
bool flag[MAXN];
int j=0;
for(int i=2;i<=n;i++)
{
   if(flag[i]==0)
    prime[j++]=i;
    for(int k=0;k<j;k++)
    {
       if(prime[k]*i>n)break;
       flag[prime[k]*i]=1;
       if(i%prime[k]==0)break;
    }
}

同余:

若a%m=b%m,则称a与B关于模m同余,记为a≡b(mod m)
性质:
(1)自反性: a≡a(mod m)
(2)对称性:若 a≡b(mod m),则 b≡a(mod m)
(3)传递性:若a≡b(mod m),b≡c(mod m),则 a≡c(mod m)
(4)同加性:若a≡b(mod m),则a+c≡b+c(mod m)
(5)同乘性:若a≡b(mod m),则a*c≡b*c(mod m)
若a≡b(mod m),c≡d(mod m),则有a*c≡b*d(mod m)
(6)同幂性:若a≡b(mod m),则an≡bn(mod m)
(7)若a%p=x,a%q=x,且p,q互质,则a%(p*q)=x

同余:

若a%m=b%m,则称a与B关于模m同余,记为a≡b(mod m)
性质:
(1)自反性: a≡a(mod m)
(2)对称性:若 a≡b(mod m),则 b≡a(mod m)
(3)传递性:若a≡b(mod m),b≡c(mod m),则 a≡c(mod m)
(4)同加性:若a≡b(mod m),则a+c≡b+c(mod m)
(5)同乘性:若a≡b(mod m),则a*c≡b*c(mod m)
若a≡b(mod m),c≡d(mod m),则有a*c≡b*d(mod m)
(6)同幂性:若a≡b(mod m),则an≡bn(mod m)
(7)若a%p=x,a%q=x,且p,q互质,则a%(p*q)=x

<同余分配率>

加法分配率:(a+b)%n=(a%n+b%n)%n
减法分配率:(a-b)%n=(a%n-b%n)%n
乘法分配率:(a*b)%n=a%n*b%n%n
除法不满意分配率,但有这特性格:(a/b)%n=a%(bn)/b

<同余分配率>

加法分配率:(a+b)%n=(a%n+b%n)%n
减法分配率:(a-b)%n=(a%n-b%n)%n
乘法分配率:(a*b)%n=a%n*b%n%n
除法不满足分配率,但有那性格格:(a/b)%n=a%(bn)/b

<剩余系>

给定n,则持有整数对n取模,将赢得多少个成团,称为模n的剩余系,即{0,1,2,……,n-1}.
n的剩余系中与n互质的数称为简化剩余系,也叫做缩系。n的剩余系记为Zn,而n的缩系记为Zn*.
模n的剩余系中,每一种成分都表示享有与它同余的平头,比如n=7,则1意味着{1,8,15,22,……},这几个集合满意模n同余关系,称为同余等价类。

<剩余系>

给定n,则拥有整数对n取模,将得到3个成团,称为模n的剩余系,即{0,1,2,……,n-1}.
n的剩余系中与n互质的数称为简化剩余系,也号称缩系。n的剩余系记为Zn,而n的缩系记为Zn*.
模n的剩余系中,每一个成分都意味着享有与它同余的整数,比如n=7,则1意味{1,8,15,22,……},那个集合满足模n同余关系,称为同余等价类。

<威尔逊定理>

若p为素数,则(p-1)!≡-1(mod p)。 其逆定理也创立。

<威尔逊定理>

若p为素数,则(p-1)!≡-1(mod p)。 其逆定理也树立。

<费马定理>

若P为素数,a为正整数,且a和P互质,则有:a^p-1≡  1(mod p)

<费马定理>

若P为素数,a为正整数,且a和P互质,则有:a^p-1≡  1(mod p)

<欧拉定理>

欧拉函数phi:不超越n的且与n互质的正整数的个数。
如果n为素数p,则 phi(p)=p-1
如果n为素数p的幂次p^a,则 phi(p^a)=(p-1)*p^(a-1).
欧拉函数为积性函数:即便n为任意三个互质的数a、b的积,则 phi(n)=
phi(a)* phi(b)

n=p1a1*p2a2*……*pkak
则  (n)=n*(1-1/p1)*(1-1/p2)*……*(1-1/pk)

欧拉定理:
若a与m互质,则710官方网站 1

<欧拉函数计算>

//法一
int euler(int n)
{
  int m=(int)sqrt(n+0.5);
  int ans=n;
for(int i=2;i<=m;i++)if(n%i==0)
{
  ans=ans/i*(i-1);
  while(n%i==0)n/=i;
}
if(n>1)ans=ans/n*(n-1);
return ans;
}

//法二(此方法更快)
int phi[maxn];
void phi_table(int n)
{
for(int i=2;i<=n;i++)phi[i]=0;
phi[1]=1;
for(int i=2;i<=n;i++)if(!phi[i])
for(int j=i;j<=n;j+=i){
if(!phi[j])phi[j]=j;
phi[j]=phi[j]/i*(i-1);
}
}

<扩充欧几里得算法>

对于随意整数a,b,一定期存款在整数x、y,使得ax+by=gcd(a,b)若gcd(a,b)=1,则终将存在整数x,y,使得ax+by=1能够行使扩展欧几Reade算法求出x,y。

void gcd(LL a,LL b,LL &d,LL &x,LL &y)
{
if(!b){x=1;d=a;y=0;}
else {
gcd(b,a%b,d,y,x);
y-=x*(a/b);
}
}

x即为a的逆元(->数学中的求导)。

运用:

(1)求二元3次方程:ax+by=c
(2)求模线性方程:ax≡b (mod n)
(3)求逆元:ab≡1 (mod n)
(4)求gcd(a,b)

<欧拉定理>

欧拉函数phi:不超过n的且与n互质的正整数的个数。
如果n为素数p,则 phi(p)=p-1
如果n为素数p的幂次p^a,则 phi(p^a)=(p-1)*p^(a-1).
欧拉函数为积性函数:如果n为任意四个互质的数a、b的积,则 phi(n)=
phi(a)* phi(b)

n=p1a1*p2a2*……*pkak
则  (n)=n*(1-1/p1)*(1-1/p2)*……*(1-1/pk)

欧拉定理:
若a与m互质,则710官方网站 2

<欧拉函数总括>

//法一
int euler(int n)
{
  int m=(int)sqrt(n+0.5);
  int ans=n;
for(int i=2;i<=m;i++)if(n%i==0)
{
  ans=ans/i*(i-1);
  while(n%i==0)n/=i;
}
if(n>1)ans=ans/n*(n-1);
return ans;
}

//法二(此方法更快)
int phi[maxn];
void phi_table(int n)
{
for(int i=2;i<=n;i++)phi[i]=0;
phi[1]=1;
for(int i=2;i<=n;i++)if(!phi[i])
for(int j=i;j<=n;j+=i){
if(!phi[j])phi[j]=j;
phi[j]=phi[j]/i*(i-1);
}
}

<扩展欧几里得算法>

对此自由整数a,b,一定期存款在整数x、y,使得ax+by=gcd(a,b)若gcd(a,b)=1,则早晚存在整数x,y,使得ax+by=1能够采用扩大欧几Reade算法求出x,y。

void gcd(LL a,LL b,LL &d,LL &x,LL &y)
{
if(!b){x=1;d=a;y=0;}
else {
gcd(b,a%b,d,y,x);
y-=x*(a/b);
}
}

x即为a的逆元(->数学中的求导)。

运用:

(1)求二元三回方程:ax+by=c
(2)求模线性方程:ax≡b (mod n)
(3)求逆元:ab≡1 (mod n)
(4)求gcd(a,b)

<模线性方程&中华夏族民共和国剩余定理>

有如下方程:

      710官方网站 3

其中n1,n2,……,nk互质。

中原剩余定理正是用来求解模线性方程组的。
对于n1,因为它与(n2*n3……*nk)互质,我们得以找到一个周全z1,使得z1*(n2*n3*……nk)%n1=1。设z1*(n2*n3*……*nk)为c1。
同理,对于各样nk,都足以找到一个zi,使得zi*(n1*n2*……*nj
|j!=i)%ni=1,设zi*(n1*n2*……*nj |j!=i)为ci。

x=b1*c1+b2*c2+……bk*ck+m(n1*n2*…*nk) 个中m为任意整数。
x为一组解。

<模线性方程&中夏族民共和国剩余定理>

有如下方程:

      710官方网站 4

其中n1,n2,……,nk互质。

中华剩余定理就是用来求解模线性方程组的。
对于n1,因为它与(n2*n3……*nk)互质,大家得以找到七个全面z1,使得z1*(n2*n3*……nk)%n1=1。设z1*(n2*n3*……*nk)为c1。
同理,对于每种nk,都得以找到3个zi,使得zi*(n1*n2*……*nj
|j!=i)%ni=1,设zi*(n1*n2*……*nj |j!=i)为ci。

x=b1*c1+b2*c2+……bk*ck+m(n1*n2*…*nk) 当中m为任意整数。
x为一组解。

<模乘法的逆>

如果(a*b)%n=1,则称a与b模n互为尾数,记为a=b^(-1)
,b=a^(-1),那是模乘法的逆。
若a与n互质,则必存在八个平头b,使得a*b%n=1,即a模n的逆元一定期存款在。
若b存在逆元,则有(a/b)%n=(a*b^(-1))%n。
    注明:设b的逆元为c,则bc%n=1
    (a/b)%n=((a/b)*bc)%n=a*c%n=a*b^(-1)%n 

 

Time:2017-02-07

 

<模乘法的逆>

如果(a*b)%n=1,则称a与b模n互为尾数,记为a=b^(-1)
,b=a^(-1),那是模乘法的逆。
若a与n互质,则必存在3个平头b,使得a*b%n=1,即a模n的逆元一定期存款在。
若b存在逆元,则有(a/b)%n=(a*b^(-1))%n。
    评释:设b的逆元为c,则bc%n=1
    (a/b)%n=((a/b)*bc)%n=a*c%n=a*b^(-1)%n 

 

Time:2017-02-07

 

相关文章