如果與唯一定理一起應用需要用到素數篩，可以看這篇文章：
線性篩判斷素數
唯一分解定理：
任何一個大于1的自然數 N,如果N不為質數，**那么N可以唯一分解成有限個質數的乘積：
這里P1<P2<P3…<Pn均為質數，其中指數ai是正整數，這樣的分解稱為 N 的標準分解式，
定理應用：
3.用唯一分解求a,b的gcd,lcm（ak,bk為質數的冪）:
4.在不取mod的情況下,用唯一分解求組合數：
解釋：
- 因子：如果a%b==0，就稱b是a的因子，例如8的因子有: 1，2，4，8；
- 因數：假如a*b=c（a、b、c都是整數)，那么我們稱a和b就是c的因數，
用代碼實作：
1.素數分解–歐拉篩(線性篩)
#define maxn 10000001
bool number[maxn+5];
ll prime[maxn/10];//素數不能開到1e7
int len;
void isprime()
{
len=0;
memset(number,true,sizeof(number));
for(int i=2; i<=maxn; i++)
{
if(number[i])
prime[len++]=i;
for(int j=0; j<len&&prime[j]*i<=maxn; j++)
{
number[prime[j]*i]=false;
if(i%prime[j]==0)
break;
}
}
}
2.唯一分解定理：
int factor[10000];
void geta(ll n)//算ai等于多少(冪指數)
{
memset(factor,0,sizeof(factor));
int cas=0;
for(int i=0;i<len&&prime[i]*prime[i]<=n;i++)
{
while(n%prime[i]==0)
{
factor[cas]++;
n/=prime[i];
}
if(factor[cas])
cas++;
}
if(n>1)//prime[i]*prime[i]<=nn當不滿足這個條件的時候就應該還有一個素數的一次方
factor[cas]=1;
}
int p[100001];
void getp(ll q)//篩出唯一分解定理的底數
{
cnt = 0;
for (int i = 2, x = q; (long long)i * i <= q; i++)//篩出q的p1，p2，p3...（唯一分解定理里面的底數）
if (!(x % i))
{
p[++cnt] = i;
while (!(x % i))
x /= i;
}
//例如q=300000時，q=2^5*3^1*5^5,此時陣列a中存盤的元素是2，3，5，cnt=3;
if (x > 1) //如果最后x大于1，即最后產生了一個小的素數，直接保存即可
p[++cnt] = x, x = 1;
}
前兩天碰到的一道codeforces上的題：
C. Division–素數篩+唯一分解定理
Pairs Forming LCM LightOJ - 1236
侵刪
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/203703.html
標籤：python
上一篇：git獲取大容量工程出錯：RPC failed； curl GnuTLS recv error : Decryption has failed.