数论当中定理
【算术基本定理】
定理:
每一个大于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),这就是费马小定理。