数论复习之费马与欧拉,费马小定理求逆元 摘自

Input

降幂!

a与n互质,当b非常大时,可用欧拉定理降幂 

(a^b) mod n = (a^(b mod phi(n))) mod n

 

终极提一下,怎么求phi(p)呢?

详见欧拉筛

需求接纳如下性质( p为质数 ):
phi(p)=p-1
因为质数p除了壹以外的因数只有p,故壹至p的平头唯有p与p不互质 

如果i mod p = 0, 那么 phi(i * p)=p * phi(i) 
若整数n 不与i互质,n+i依然与i不互质
若整数n与i互质,n+i与i依旧互质,注脚:

若i mod p ≠0,  那么 phi( i * p )=phi(i) * ( p-1 )
i mod p 不为0且p为质数, 所以i与p互质, 那么依照欧拉函数的积性 phi(i *
p)=phi(i) * phi(p)  个中phi(p)=p-一即首先条性质

#include<iostream> 
#include<cstdio> 
#define N 40000 
using namespace std; 
int n; 
int phi[N+10],prime[N+10],tot,ans; 
bool mark[N+10]; 
void getphi() 

         int i,j; 
         phi[1]=1; 
         for(i=二;i<=N;i++)//也就是分解质因式的逆进度 
         { 
                  if(!mark[i]) 
                            { 
                                  
 prime[++tot]=i;//筛素数的时候首先会剖断i是或不是是素数。 
                                    phi[i]=i-1;//当 i 是素数时
phi[i]=i-1 
                                    } 
                  for(j=1;j<=tot;j++) 
                  { 
                           if(i*prime[j]>N)  break
                         
 mark[i*prime[j]]=1;//确定i*prime[j]不是素数 
                         
 if(i%prime[j]==0)//接着大家会看prime[j]是否是i的约数 
                           { 
                                  
 phi[i*prime[j]]=phi[i]*prime[j];break
                           } 
                           else 
phi[i*prime[j]]=phi[i]*(prime[j]-一);//其实那里prime[j]-1就是phi[prime[j]],利用了欧拉函数的积性 
                  } 
         } 

int main() 
{
         getphi(); 
}

 

计算一下: 简言之,除以一个数取模的话,和乘以这些数的逆元取模效果是如出一辙的。
求逆元其实正是求使A*X = 1 (mod
C)
树立的X,当中A是除法中的除数(貌似又要扯到扩欧、、)

求解除法取模问题(a/b)%m,大家能够转成(a*b’)mod m来解决,其中b’是b的逆元

 

降幂、
a与n互质,当b异常的大时,可用欧拉定理降幂 

(a^b) mod n = (a^(b mod phi(n))) mod n

 

一.费马小定理 Fermat 西奥ry

如果 p是素数,且a与p互质,即gcd(a,p)=1   那么(a^p-1) ≡ 1 (mod
p)

应用: 求乘法逆元

 

*乘法逆元:
(x\
x’)≡ 1 (mod p) 称x’为x模p的乘法逆元 (注意,一定就算余一)

逆元 :(b/a) (mod n) = (b * x) (mod n)。 x表示a的逆元。并且 a*x ≡ ①(mod n)  注意:唯有当a与n互质的时候才存在逆元

留意,逆元也得以如此驾驭,求三个比很小的正整数x(逆元),使a乘以x对m的取余等于一对m的取余,
所以m=1 时,逆元为1

 

因为(a^p-1) ≡ 1 (mod p) 那么 (a*a^p-2)≡ 1 (mod p) 
所以 a^p-2就是a关于模p的乘法逆元

 

逆元用处:

在求解除法取模难点(a/b)%m时,大家得以转账为(a%(b∗m))/b, 
可是1旦b非常大,则会现出爆精度难题,所以大家幸免使用除法直接总结。 
能够行使逆元将除法转换为乘法: 
借使b存在乘法逆元,即与m互质(充要条件)。设c是b的逆元,即b∗c≡壹(mod
m),那么有a/b=(a/b)∗壹<=>(a/b)∗b∗cóa∗c (mod m) 
即,除以3个数取模等于乘以这几个数的逆元取模。

 

于是乎求(a/b)mod p 就退换为求(a*b’)mod p =( (a mod p)*(b^p-2 mod p) )mod
p

适用于P为质数

 

#include<bits/stdc++.h>
#define int __int64  
using namespace std;
int tt[2000],mod,cnt;

int phi(int n)
{
    int m=(int)sqrt(n+0.5),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;
}

void find(int n)
{
    int m=(int) sqrt(n+0.5);
    tt[++cnt]=n;
    for(int i=2;i<=m;i++)
    {
        if(i*i==n) tt[++cnt]=i;
        else if(n%i==0) tt[++cnt]=i,tt[++cnt]=n/i;
    }
}

int Pow(int n,int k)//×¢Òâ´óд·ñÔò»á³åÍ» 
{
    int ans=1;
    while(k)
    {
        if(k&1) ans=(ans*n)%mod;
        n=(n*n)%mod,k>>=1;
    }
    return ans%mod;
}

main()
{
    int n;
    while(cin>>n)
    {
        if(n==1||!(n&1))
             {cout<<"2^? mod "<<n<<" = 1"<<endl;continue;}
        int m=phi(n),ans=0;
        cnt=0,find(m),mod=n;
        sort(tt+1,tt+1+cnt);
        for(int i=1;i<=cnt;i++)
        {
            if(Pow(2,tt[i])==1)
            {ans=tt[i];break;}
        }
        cout<<"2^"<<ans<<" mod "<<n<<" = 1"<<endl;  
    }
    return 0;
}

三.欧拉定理

若a,n为正整数,且a,n互质(即gcd(a,n)=1),则有:

a^φ(n)≡ 1 (mod n)

听新闻说此定理,费马小定理即为分明,因为质数p的phi(p)就等于p-一

 

应用:

QB_UDG  2016年11月8日10:16:18

Sample Output

一.费马小定理 Fermat 西奥ry

如果 p是素数,且a与p互质,即gcd(a,p)=1   那么(a^p-1) ≡ 1 (mod
p)

应用: 求乘法逆元

 

*乘法逆元:
(x\
x’)≡ 1 (mod p) 称x’为x模p的乘法逆元 (注意,一定假使余1)

逆元 :(b/a) (mod n) = (b * x) (mod n)。 x表示a的逆元。并且 a*x ≡ 一(mod n)  注意:唯有当a与n互质的时候才存在逆元

注意,逆元也足以如此敞亮,求三个小小的正整数x(逆元),使a乘以x对m的取余等于①对m的取余,
所以m=1 时,逆元为一

 

因为(a^p-1) ≡ 1 (mod p) 那么 (a*a^p-2)≡ 1 (mod p) 
所以 a^p-2就是a关于模p的乘法逆元

 

逆元用处:

在求解除法取模难点(a/b)%m时,大家得以转账为(a%(b∗m))/b, 
但是假使b极大,则晤面世爆精度难点,所以我们幸免选用除法直接计算。 
能够利用逆元将除法调换为乘法: 
借使b存在乘法逆元,即与m互质(充要条件)。设c是b的逆元,即b∗c≡一(mod
m),那么有a/b=(a/b)∗1<=>(a/b)∗b∗cóa∗c (mod m) 
即,除以1个数取模等于乘以那些数的逆元取模。

 

于是求(a/b)mod p 就更改为求(a*b’)mod p =( (a mod p)*(b^p-2 mod p) )mod
p

适用于P为质数

 

2.欧拉函数 对此多个正整数x,小于x且和x互质的正整数的个数,记做:φ(x)  当中φ(壹)被定义为1,但是并未其他实质的意义

通式1:φ(x)=x*(1-  1/p1)***(1-  1/p2)*(1- 
1/p3)*…..*(1-  1/pn) 
内部p一, p二,p3……pn为x的具备质
因数**

通式2:若x是质数p的k次幂,即x=p^k,有φ(x) = p^k – p^(k-1) =
(p-1)*p^(k-1) 
因为x的质因数唯有p,所以除了p的翻番外,别的数都跟x互质。(程序中大家一般将φ(x)写成phi(x))。

 

 

性质:

1.若x,y互质(即gcd(x,y)=1),那么φ(x*y)=φ(x)*φ(y) 
2.若x是奇数φ(2x)=φ(x) 
3.若x是质数φ(x)=x-1 
4.若x>2,φ(x)为偶数

上述四条均能够依照欧拉函数推出!且显明!

 

不写了,见小编前边的博客。

数论复习之费马与欧拉

3.欧拉定理

若a,n为正整数,且a,n互质(即gcd(a,n)=1),则有:

a^φ(n)≡ 1 (mod n)

传说此定理,费马小定理即为显明,因为质数p的phi(p)就相当p-1

 

应用:

#include<bits/stdc++.h>
using namespace std;
int mod=17,inv[30];

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

void output()
{
    for(int i=1;i<=20;i++)
        cout<<inv[i]<<" ";
}

int main()
{
    init();
    output();
    return 0;
}

QB_UDG  2016年11月8日10:16:18

降幂!

a与n互质,当b不小时,可用欧拉定理降幂 

(a^b) mod n = (a^(b mod phi(n))) mod n

 

末段提一下,怎么求phi(p)呢?

详见欧拉筛

须求动用如下性质( p为质数 ):
phi(p)=p-1
因为质数p除了一以外的因数唯有p,故1至p的平头唯有p与p不互质 

如果i mod p = 0, 那么 phi(i * p)=p * phi(i) 
若整数n 不与i互质,n+i依然与i不互质
若整数n与i互质,n+i与i依旧互质,声明:

若i mod p ≠0,  那么 phi( i * p )=phi(i) * ( p-1 )
i mod p 不为0且p为质数, 所以i与p互质, 那么依照欧拉函数的积性 phi(i *
p)=phi(i) * phi(p)  个中phi(p)=p-一即首先条性质

#include<iostream> 
#include<cstdio> 
#define N 40000 
using namespace std; 
int n; 
int phi[N+10],prime[N+10],tot,ans; 
bool mark[N+10]; 
void getphi() 

         int i,j; 
         phi[1]=1; 
         for(i=二;i<=N;i++)//也就是分解质因式的逆进程 
         { 
                  if(!mark[i]) 
                            { 
                                  
 prime[++tot]=i;//筛素数的时候首先会决断i是还是不是是素数。 
                                    phi[i]=i-1;//当 i 是素数时
phi[i]=i-1 
                                    } 
                  for(j=1;j<=tot;j++) 
                  { 
                           if(i*prime[j]>N)  break
                         
 mark[i*prime[j]]=1;//确定i*prime[j]不是素数 
                         
 if(i%prime[j]==0)//接着大家会看prime[j]是否是i的约数 
                           { 
                                  
 phi[i*prime[j]]=phi[i]*prime[j];break
                           } 
                           else 
phi[i*prime[j]]=phi[i]*(prime[j]-一);//其实那里prime[j]-1就是phi[prime[j]],利用了欧拉函数的积性 
                  } 
         } 

int main() 
{
         getphi(); 
}

 

小结一下: 轻易,除以三个数取模的话,和乘以这几个数的逆元取模效果是千篇一律的。
求逆元其实正是求使A*X = 1 (mod
C)
树立的X,个中A是除法中的除数(貌似又要扯到扩欧、、)

求解除法取模难题(a/b)%m,大家能够转成(a*b’)mod m来解决,其中b’是b的逆元

 

降幂、
a与n互质,当b一点都不小时,可用欧拉定理降幂 

(a^b) mod n = (a^(b mod phi(n))) mod n

 

图片 1

二.欧拉函数 对此一个正整数x,小于x且和x互质的正整数的个数,记做:φ(x)  个中φ(一)被定义为1,可是并未有别的实质的意思

通式1:φ(x)=x*(1-  1/p1)***(1-  1/p2)*(1- 
1/p3)*…..*(1-  1/pn) 
内部p1, p二,p叁……pn为x的装有质
因数**

通式2:若x是质数p的k次幂,即x=p^k,有φ(x) = p^k – p^(k-1) =
(p-1)*p^(k-1) 
因为x的质因数只有p,所以除了p的翻番外,其余数都跟x互质。(程序中大家一般将φ(x)写成phi(x))。

 

 

性质:

1.若x,y互质(即gcd(x,y)=1),那么φ(x*y)=φ(x)*φ(y) 
2.若x是奇数φ(2x)=φ(x) 
3.若x是质数φ(x)=x-1 
4.若x>2,φ(x)为偶数

以上4条均能够依照欧拉函数推出!且鲜明!

 

数论复习之费马与欧拉

a是不能够被质数p整除的正整数,则有a^(p-壹) ≡ 一 (mod
p)
阐明那些定律卓殊轻松,由于φ(p) = p-1,代入欧拉定理就能够验证。
一样有推论:对于不可能被质数p整除的正整数a,有a^p ≡ a (mod p)

 正解

逆元模板题 hdu1576

费马小定理

摘自互联网

线段树HDU5475

 

费马小定理求逆元 摘自guhaiteng

渴求(A/B)%997三,但出于A比比较大,我们只给出n(n=A%997三)(我们加以的A必能被B整除,且gcd(B,997叁)
= 一)。

 hdu1395强力水过了。。正解神速幂,欧拉函数

2 1000 53 87 123456789

图片 2

搜过来的难点试求逆元,可是细想开掘不对劲,因为你除再取mod是不得以的(能够想转手为什么),于是自个儿就不精通如何是好了,看了互连网的题解奇妙的觉察是线段树???然后单点更新,维护乘积就足以了。。

对应每组数据输出(A/B)%997三

图片 3

 on求出1~n 的逆元

逆元,摘自SssssssBbbbbbbb

#include<bits/stdc++.h>
#define mid (l+(r-l)/2)
#define ls (rt<<1)
#define rs (rt<<1|1)
#define int long long
using namespace std;
int tr[500000<<2],n,t,mod,t1,t2;

void build(int l,int r,int rt)
{
    tr[rt]=1;if(l==r) return ;
    build(l,mid,ls),build(mid+1,r,rs);
}
void update(int l,int r,int rt,int L,int C)
{
    if(l==r){tr[rt]=C;return ;}
    if(L<=mid) update(l,mid,ls,L,C);
    else update(mid+1,r,rs,L,C);
    tr[rt]=(tr[ls]*tr[rs])%mod;
}

main()
{
    scanf("%lld",&t);
    for(int kkk=1;kkk<=t;kkk++)
    {
        printf("Case #%lld:\n",kkk);
        cin>>n>>mod;
        build(1,n,1);
        for(int i=1;i<=n;i++)
        {
            scanf("%lld%lld",&t1,&t2);
            if(t1==1) update(1,n,1,i,t2);
            if(t1==2) update(1,n,1,t2,1);
            cout<<tr[1]%mod<<"\n";
        }
    }
    return 0;
}

图片 4

Output

Sample Input

#include<bits/stdc++.h>
using namespace std;


int main()
{
    int n;
    while(cin>>n)
    {
        if(n==1||!(n&1))
            {printf("2^? mod %d = 1\n",n);  continue;}
        for(int j=1,mi=2;;mi<<=1,j++,mi%=n)
            if(mi%n==1)  
            {  
                printf("2^%d mod %d = 1\n",j,n);  
                break ;  
            }
    }
    return 0;
}

写的时候不明白scanf
%lld为何萎了,然后就用cin水过去了。。本感觉会卡时间。。

 

数据的首先行是贰个T,表示有T组数据。
每组数占领五个数n(0 <= n < 9973)和B(一 <= B <= 10^九)。

 欧拉定理的求证

#include<bits/stdc++.h>
#define int long long
using namespace std;
int b,a;

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

int inv(int a,int n)
{
    int d,x,y;
    exgcd(a,n,d,x,y);
    return d==1?(x+n)%n:-1;
}

main()
{
    int n;
    cin>>n;
    while(n--)
    {
        cin>>a>>b;
        int x=inv(b,9973);
        printf("%lld\n",(a*x)%9973);
    }
    return 0;
}

 

 

 

欧拉函数

 

7922 6060

Problem Description

图片 5

相关文章