【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开心