【UVa1635】唯一分解定理 + 組合數遞推

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <climits>
#include <utility>
#include <cmath>
using namespace std;

const int MAXN =  + ;

int n, m;

void fenjie(vector< pair<int, int> > &N)
{
    int tmp = m;
    int t = sqrt(m + );
    //printf("t = %d\n", t);
    for (int i = ; i <= t; i++)
    {
        if (tmp % i == )
        {
            int c = ;
            while (tmp % i == )
            {
                tmp /= i;
                c++;
            }
            N.push_back(make_pair(i, c));
        }
    }

    if (tmp > )
    {
        N.push_back(make_pair(tmp, ));
    }
}

bool youguan[MAXN];

int main()
{
    while (scanf("%d %d", &n, &m) == )
    {
        memset(youguan, false, sizeof(youguan));
        vector< pair<int, int> > yinshu;
        fenjie(yinshu);
        /*for (int i = 0; i < (int)yinshu.size(); i++)
        {
            printf("%d %d\n", yinshu[i].first, yinshu[i].second);
        }*/

        n--;

        for (int i = ; i < (int)yinshu.size(); i++)
        {
            int t = yinshu[i].first, e = ;
            for (int k = ; k < n; k++)
            {
                int up = n - k + ;
                while (up % t == )
                {
                    up /= t;
                    e++;
                }

                int down = k;
                while (down % t == )
                {
                    down /= t;
                    e--;
                }

                if (e < yinshu[i].second)
                {
                    youguan[k] = true;
                }
            }
        }

        vector<int> ans;
        for (int i = ; i < n; i++)
        {
            if (youguan[i] == false)
            {
                ans.push_back(i + );
            }
        }

        printf("%d\n", (int)ans.size());
        if (!ans.empty())
        {
            for (int i = ; i < int(ans.size() - ); i++)
            {
                printf("%d ", ans[i]);
            }
            //printf("%d\n", ans.back());
            printf("%d", ans[ans.size() - ]);
        }
        printf("\n");
    }

    return ;
}
           

終于過了，我也不想寫什麼了，A題真開心。

算了我來說說我的心路曆程。

1、要去看原題面，紫書上的題面看不懂TvT

光看紫書是真的不知道這題要幹什麼？無關是什麼意思？

實際上原題面的意思是這樣的讓我這個用谷歌翻譯看題面的人臭不要臉地來說說：

題面上的人，就叫小明吧，發明出了一種求0～m-1中的随機數的方法。在0～m-1中取n個随機整數，讓每個數和它右邊的數相加得到一個新數，這樣就剩下了n-1個數，一直這樣做知道隻剩下1個數，這個數%m就是生成的随機數。

他興緻勃勃地把這個方法告訴老師，然後老師說不行啊你還是naive，這樣生成的數首先有一個缺點就是它和你一開始取的用來得到它的那n個整數有的根本就沒有關系的呀！比如說n=3，m=2，那最後的這個數就和a2沒有關系【就是說不管a2是什麼都不影響最後的結果】

2、方法我看了這個部落格和紫書上的講解，很好懂，其實不難。部落格上說這道題可以總結出一個利用唯一分解定理判斷能否整除m的一個方法，這樣就不需要高精度了。有點妙欸。

3、分解質因數的方法有點妙，對就是國小學的倒除法。我這才知道倒除法不僅能求gcd還能求lcm還能求它的質因數！好強呀。

4、不過我覺得這道題最妙的還是組合數遞推的時候【遞推式：c(n, k) = c(n, k-1) * (n-k+1) / k】，他沒有直接乘起來遞推，那樣不僅有可能爆int還會T【應該是】，他是把遞推的時候的次數全都累積起來，這樣就隻需要再算新的系數(n-k+1)/k中又有多少新的次數就行了。【我剛想明白！開心！】

5、我後來交的時候出現了Presentation error，第一次遇到hhhh，是輸出格式不正确，第二行最後多了個空格。結果改了之後RE，是最後ans有可能為空。最後終于A啦hhhh開心