当前位置: 代码迷 >> 综合 >> 数论当中定理
  详细解决方案

数论当中定理

热度:5   发布时间:2024-01-15 07:52:39.0

数论当中定理

【算术基本定理】

定理:

每一个大于1的正整数n都可以唯一地写成素数的乘积,在乘积中的素因子按照非降序排列,正整数n的分解式n=(p1^α1)*(p2^α2)*(p3^α3)* ....... *(pk^αk)称为n的标准分解式,其中p1,p2,p3......pk是素数,p1<p2<p3.....,且α1,α2,α3.......是正整数。

性质:

(1)设d(n)为n的正因子的个数,则有d(n)=(α1+1)*(α2+1)*(α3+1)*......*(αk+1) (p1可以取0~α1个,有α1+1种取法,同理p2有α2+1种取法)

(2)设f(n)为n的所有因子之和,则有f(n)=【(p1^α1)-1】/(p1-1 * 【(p2^α2)-1】/(p2-1) * .....  *【(pk^αk)-1】/(pk-1)

(3)n! 的素因子分解中的素数p的指数(幂)为【n/p】+【n/p^2】+【n/p^3】+.......

应用一:点这里

应用二:点这里

应用三:点这里

唯一分解定理模板:

void init(LL m)
{sum = 0;LL tmp = m;for(LL i = 2; i*i<=tmp; i++)    //官方版的唯一分解定理if(tmp%i==0){fac[sum++] = i;while(tmp%i==0) tmp /=  i;}if(tmp>1) fac[sum++] = tmp;
}

int p[1005], c[1005]; 
ll cnt;//因子个数 
const ll N = 1e6+10; 
ll prime[N] = {0},num_prime = 0;  //prime存放着小于N的素数   
int isNotPrime[N] = {1, 1};        // isNotPrime[i]如果i不是素数,则为1 
int Prime()    
{     for(ll  i = 2 ; i < N ; i ++)       {            if(! isNotPrime[i])               prime[num_prime ++]=i;  //无论是否为素数都会下来     for(ll  j = 0 ; j < num_prime && i * prime[j] <  N ; j ++){               isNotPrime[i * prime[j]] = 1;  if( !(i % prime[j] ) )  //遇到i最小的素数因子//关键处1                  break;           }        }        return 0;   
}  
///与素数筛选一起用的质数分解
///将x分解为式n=(p1^α1)*(p2^α2)*(p3^α3)* ....... *(pk^αk)
///数组p和c求解保存底数p1或者指数α1void Dec(ll x)
{cnt = 0;for(int i=0; prime[i]*prime[i]<=x&&i<num_prime; i++){if(x%prime[i]==0){int num=0;while(x%prime[i]==0){num++;x /= prime[i];} p[cnt]=prime[i];c[cnt++]=num;}if(x==1) break;}if(x > 1) {p[cnt]=x;c[cnt++] = 1;   }}

应有:LightOJ - 1220 Mysterious Bacteria 唯一分解定理

【威尔逊定理】

 

定理:当且仅当p为质数,p可整除(p-1)!+1,即(p-1)! ≡ p-1 ≡ -1(mod p)

其逆定理也成立:对于某一正整数p,如果(p-1)! ≡ p-1 ≡ -1(mod p),则p一定是素数

应用:点这里

 

 【欧拉定理】

    若正整数 a , n 互质,则  a^φ(n)≡1(mod n)   其中 φ(n) 是欧拉函数(1~n) 与 n 互质的数。

 

欧拉定理的推论:

  若正整数a,n互质,那么对于任意正整数b,有a^b≡a^(b mod φ(n))(mod n)

 

【费马定理】

假如p是质数,且gcd(a,p)=1,那么a^(p-1) ≡1(mod p),,即 ( a^(p-1) )%p = 1。

一般情况下,若p为素数,a^p ≡a(mod p),这就是费马小定理。

 

  相关解决方案