UVa1635 - Irrelevant Elements

通过观察发现其规律符合杨辉三角

需要注意的是最后ai的系数是C（i-1,n-1）

那么，问题就可以变成判断C（0，n-1），C（1，n-1）。。。。C（n-1，n-1）哪些是m的倍数

只需要计算出m的唯一分解式中各个素因子在C(i-1,n-1)中的指数即可完成判断

然而为了节省时间，实际上我们只需算出m的每一个素因子在C（i-1，n-1）项中含有几个即可

即我们将c(i-1,n-1)依次除以m的每一个素因子，直到无法整出，即可得出该项素因子的个数

紫薯上给出一个公式C(k,n)=（n-k+1）*c(k-1,n)/k

可以用这个公式递推出所要求出的素因子的个数

具体怎么做呢？

说明：f[i].first中存的时m的素因子，f[i].second中存的是其对应的个数

d[i]用来存c(i-1,n-1)中素因子的个数

int d[50]={0};
for (int k=;k<=n;k++){

        int x=n-k+;

        for (int i=;i<f.size();i++){

            int p=f[i].first;

            d[i]+=x/p;

            x%=p;

        }

        x=k-;

        for (int i=;i<f.size();i++){

            int p=f[i].first;

            d[i]-=x/p;

            x%=p;

        }

        int flag=;

        for (int i=;i<f.size();i++){

            if (d[i]<f[i].second) {flag=;break;}

        }

        if (flag) cout<<k<<" ok"<<endl;else cout<<"no"<<endl;

    }

注意精度问题，所以采用分开除的方法。例外注意是利用的d[i]这个数组的生存周期是在总的循环里实现的递推

这里给出网上某大神的优秀代码

转：http://blog.csdn.net/u014800748/article/details/43927205

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>

#include<algorithm>

#include<string>

#include<sstream>

#include<set>

#include<vector>

#include<stack>

#include<map>

#include<queue>

#include<deque>

#include<cstdlib>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<ctime>

#include<functional>

using namespace std;

#define N 100005

int fac[][];//一张表，fac[i][0]存放素因数，fac[i][1]存放其指数

int fac_c[];

int a[N];

void factor(int m)//分解m

{

    int&num = fac[][];//fac[0][0]是表头，存放总的个数，用引用比较方便

    num = ;

    for (int i = ; i*i <= m;i++)

    if (m%i == )

    {

        fac[++num][] = i;

        fac[num][] = ;

        do

        {

            fac[num][]++;

            m /= i;

        } while (m%i == );//将i除干净

    }

    if (m > )//如果分解到最后m仍然大于1,说明它是一个素数。注意：如果只是判断素因子有哪些，可以没有此处判断，否则必须有此步

    {

        fac[++num][] = m;

        fac[num][] = ;

    }

}

bool check(int n, int j)//按照递推公式来计算第j项，检查唯一分解式的指数

{

    int num = fac[][];

    int a = n - j;//其实是((n-1)+j+1)化简后的结果

    int b = j;

    for (int i = ; i <= num; i++)

    {

        int p = fac[i][];

        int&q = fac_c[i];

        for (; a%p == ; a /= p, q++);//为了提高效率，只用检验m的分解式中的素因数即可

        for (; b%p == ; b /= p, q--);

    }

    for (int i = ; i <= num;i++)

    if (fac[i][] > fac_c[i])

        return false;

    return true;

}

int main()

{

    //freopen("test.txt", "r", stdin);

    int n, m;

    while (cin >> n >> m)

    {

        int cnt = ;

        factor(m);

        memset(fac_c, , sizeof(fac_c));

        for (int i = ; i < n;i++)//直接检查1到n-1项（从0开始）

        if (check(n, i))

            a[cnt++] = i + ;

        printf("%d\n", cnt);

        for (int i = ; i < cnt; i++)

            printf("%s%d", i ==  ? "" : " ", a[i]);

        printf("\n");

    }

    return ;

}

巴特西

UVa1635 - Irrelevant Elements

最新文章

热门文章