vjudge鏈接

原題鏈接

乍一看似乎沒(méi)什么思路，但是寫幾個(gè)簡(jiǎn)單的例子之后規(guī)律就變得很明顯。
比如當(dāng) n=5 時(shí)，每一步計(jì)算后的結(jié)果如下：

a₁
a₁+a₂
a₁+2a₂+a₃
a₁+3a₂+3a₃+a₄
a₁+4a₂+6a₃+4a₄+a₅

顯然系數(shù)“1, 4, 6, 4, 1”就是楊輝三角第五行。
故某一項(xiàng)的系數(shù)是否是題中 m 的倍數(shù)，就決定了最終得到的數(shù)除以 n 的余數(shù)和那一項(xiàng)是否有關(guān)。

二項(xiàng)式定理：

二項(xiàng)式定理

從中很容易得到前后兩項(xiàng)的關(guān)系 C(n, k)=(n-k+1)/k*C(n, k-1) 。但是單純用這個(gè)公式暴力得到每個(gè)系數(shù)一定會(huì)導(dǎo)致溢出，故需要運(yùn)用唯一分解定理分別存儲(chǔ)每個(gè)系數(shù)的素因數(shù)和指數(shù)。
一般的代碼不難給出，但是一直TLE。最后發(fā)覺(jué)應(yīng)該先分解 m ，再得到 m 的素因數(shù)在各個(gè) C(n,k) 中的指數(shù)，若指數(shù)過(guò)小則可以提前結(jié)束當(dāng)前的分解。由于 m>1 ，可以忽略 n==k 和 n==0 的情況。
我的 AC 代碼如下，最初是用 ANSI C 寫的，一步一步改過(guò)來(lái)，故非常不簡(jiǎn)潔。其中用 map 存儲(chǔ)素因數(shù)，其中元素 -1 用來(lái)作為該項(xiàng)是否能被 m 整除的 flag。

/*
 *lang C++ 5.3.0
 *user Weilin_C
*/
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <sstream>
#include <vector>
#include <map>
//#include <unordered_map>
#include <set>
#include <list>
#include <queue>

//每個(gè)數(shù)用map分質(zhì)因數(shù)存儲(chǔ)
//質(zhì)數(shù)用素?cái)?shù)篩 2-1000000000, MAXM=1000000
#define MAXM 1000000
#define MAXN 100000+5
using namespace std;

map <int, int> sta[MAXN], mm;
int pos[MAXN];
int prime[MAXM+1];

void mtomap (map<int, int> *ma, int n, int p)
{   //解碼m n: 解碼的數(shù) p: 數(shù)n的個(gè)數(shù)
    int num=n;
    for (int i=2; i<=MAXM && num>0; i++) {
        if (!prime[i]) {
            while (num%i==0 && num>0) {
                num/=i;
                (*ma).insert(pair<int, int>(i, 0));
                (*ma)[i]+=p;
            }
        }
    }
    if (num>1) (*ma).insert(pair<int, int>(num, 1));

    return;
}

void ntomap (map<int, int> *ma, int n, int p)
{   //用于逐個(gè)解碼第n行的楊輝三角 n: 解碼的數(shù) p: 數(shù)n的個(gè)數(shù)
    map <int, int>::iterator it;
    int num=n, t;
    if (n<2) return;
    for (it=mm.begin(); it!=mm.end(); it++) {
        t=it->first;
        if (t<2) continue;
        (*ma).insert(pair<int, int>(t, 0));
        while (num%t==0 && num>0) {
            num/=t;
            (*ma)[t]+=p;
        }
        if ((*ma)[t]<it->second) (*ma)[-1]=0;
    }

    return;
}

int judge(map<int, int> *ma)
{   //是否為0或1
    int flag=0;
    map <int, int>::iterator it;
    for (it=(*ma).begin(); it!=(*ma).end(); it++)
        if (it->second!=0 && it->first!=-1) {
            flag=1;
            break;
        }
    return flag;
}

int main()
{
    int m, n;

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    /* C(n, k) = (n-k+1)/k * C(n, k-1) */
    
    for (int i=2; i<=sqrt(MAXM+1); i++) {
        if (prime[i]) continue;
        for (int j=i+i; j<=MAXM; j+=i) prime[j]=1;
    }

    while (scanf("%d%d", &n, &m)==2) {  //n: 楊輝三角層數(shù)
        //printf("%d %d\n", n, m);
        for (int i=0; i<=n; i++) if (!sta[i].empty()) sta[i].clear();
        mm.clear();
        sta[0][m]=0;
        sta[0][-1]=0;

        mtomap(&mm, m, 1);

        map <int, int>::iterator it;
        for (int i=1; i<n; i++) {
            for (it=sta[i-1].begin(); it!=sta[i-1].end(); it++) sta[i][it->first]=it->second;
            sta[i][-1]=1;
            ntomap(&sta[i], n-i, 1);
            ntomap(&sta[i], i, -1);
        }

        pos[0]=0;
        int ans=0;
        for (int i=0; i<n; i++) {
            if (sta[i][-1] && judge(&sta[i])) {
                ans++;
                pos[++pos[0]]=i+1;
            }
        }
        printf("%d\n", ans);
        int f=0;
        for (int i=1; i<=pos[0]; i++) {
            if (f) putchar(' ');
            else f=1;
            printf("%d", pos[i]);
        }
        putchar('\n');
    }

    return 0;
}

by SDUST weilinfox
本文鏈接：http://www.itdecent.cn/p/a8c34006ce31