uva 10375 唯一分解定理 篩法求素數[數論]

uva 10375 唯一分解定理 篩法求素數[數論]

唯一分解理論的基本內容：

任意一個大於1的正整數都能表示成若干個質數的乘積，且表示的方法是唯一的。換句話說，一個數能被唯一地分解成質因數的乘積。因此這個定理又叫做唯一分解定理。

舉個栗子：50=(2^1)*(5^2)

題目一般的思路就是要把素數表打出來，eg上面的例子 e={1,0,2,0,0......}

下面是兩個題目，僅說說大致的思想：

題目一：

E=(X1*X3*X4* ...*Xk)/X2 判斷E是不是整數

如果把(X1*X3*X4* ...*Xk)分解成素數相乘，將X2也分解成素數相乘，那麼如果(X1*X3*X4* ...*Xk)能整除X2 則每一個素數的指數，必然是(X1*X3*X4* ...*Xk)中大於X2中，若有一個小於，則說明不是整數了。

題目二：

已知C（m，n）=m！/（n！(m-n！))，輸入整數p，q，r，s，（p>=q，r>=s，pqrs<10000），計算C（p，q）/C（r，s），輸出保證不超過10^8，保留五位小數。

初次看見這個題目是沒有什麼思路的，然後學了唯一分解理論之後有了一定的想法，

我們這樣來想這個問題：我們把C（p，q）/C（r，s）=(p！*s！*（r-s）！)/(q！*（p-q）！*r！)

C(p,q)/C(r,s) = [ p*(p-1)...(p-q+1) * s! ] / [ r*(r-1)....(r-s+1)*q! ]

但是不能全部乘起來再除（爆），也不能一邊乘一邊除（精度），把每個數字分解質因子，分子中分解出來的質因子，個數增加，分母分解出來的質因子，個數減少

最後查看所有的質因子，個數為正的要乘，個數為負的要除，要一邊乘一邊除否則又會爆

那麼應該怎麼寫呢，根據以上講的知識應該很容易理解思想了吧.......

下面附渣代碼

#include
#include
#include
#include
#include
using namespace std;
#define maxn 10005
int e[maxn];

/**e代表的是各個素數的系數
prime代表的是{2,3,5,7,11......}*/


/**vis數組標記為0則說明是素數*/
int vis[maxn];
void getPrimevis(int n)
{
    int m=sqrt(n+0.5);
    memset(vis,0,sizeof(vis));
    for(int i=2; i<=m; i++)
        for(int j=i*i; j<=n; j+=i) vis[j]=1;
}

/**prime數組:prime[]={2,3,5,7,11,13......}*/
vectorprime;
void getprimeprime(int n)
{
    for(int i=2; i<=n; i++)
        if(vis[i]==0) prime.push_back(i);
}


//將n變為素數存在e數組裡面，對e數組進行一個加減的操作
void add_integer(int n,int d)
{
    for(int i=0; i>p>>q>>r>>s)
    {
        memset(e,0,sizeof(e));
        add_factorial(p,1);
        add_factorial(q,-1);
        add_factorial(p-q,-1);
        add_factorial(r,-1);
        add_factorial(s,1);
        add_factorial(r-s,1);
        double ans=1;
        for(int i=0; i