我們很容易發現最后每一項的系數就是二項式展開，余數和m沒有關系就意味著可以被m整除，因此我們就需要求出每一個二項式的系數。但是數據實在太大我們根據唯一分解定理將m和系數都進行分解，然后比較因子的冪。

二項式的計算我們可以根據楊輝三角遞推，可是這個實在是太大了，遞推很慢。
所以我們要知道二項式的另一個遞推式：C(n,k)=C(n,k-1)*(n-k+1)/k,遞推出需要的素數的分解式。

我們發現判斷每一個系數是否能夠被m整除需要將所有的因子進行比較，如果不處理的話10⁹需要10⁵ 的素數表，每一次都是10⁵的比較，這樣太耗時了，很多操作都是沒有意義的（因為m根本沒有那么多因子）。為了優化，我們用一個表記錄m的所有素因子和每個因子出現的次數，然后再用另一個數組記錄系數中這些因子出現的次數，這樣就可以大大提升時間效率。

輸出為0的時候要多輸出一個換行，需要注意。

#include<cstdio> #include<cstring> #include<algorithm> #include<climits> #include<cctype> #include<queue> #include<set> #include<cmath>using namespace std;typedef long long ll; const int INF=0x3f3f3f3f; const int MAXN=1e5+5; bool check[MAXN]; int prime[MAXN]; int cnt1[MAXN]; int cnt2[MAXN]; int tmp[MAXN]; int ans[MAXN]; int num,tot,top; int n,m;void creat_prime() {tot=0;for(int i=2;i<MAXN;i++){if(!check[i]) prime[tot++]=i;for(int j=0;j<tot && prime[j]*i<MAXN ;j++){check[prime[j]*i]=true;if(i%prime[j]==0) break;}} }bool ok() {for(int i=0;i<top;i++){if(cnt2[i]>tmp[i]) return false;}return true; }void deal(int x,int d) {for(int i=0;i<top;i++){while(x%cnt1[i]==0){tmp[i]+=d;x/=cnt1[i];}if(x==1) break;} }int first=1;int main() {//freopen("data.out","w",stdout);creat_prime();while(~scanf("%d%d",&n,&m)){num=0; top=0;memset(cnt2,0,sizeof(cnt2));for(int i=0;i<tot;i++){if(m%prime[i]==0){cnt1[top]=prime[i];while(m%prime[i]==0){cnt2[top]++;m/=prime[i];}top++;}if(m==1) break;}if(m!=1){cnt1[top]=m;cnt2[top]++;top++;}memset(tmp,0,sizeof(tmp));for(int i=1;i<n-1;i++){deal(n-i,1);deal(i,-1);if(ok()){ans[num++]=i+1;}} // if(first) first=0; // else printf("\n");printf("%d\n",num);if(num==0){printf("\n");continue;}for(int i=0;i<num-1;i++){printf("%d ",ans[i]);}printf("%d\n",ans[num-1]);}return 0; }

總結

以上是生活随笔為你收集整理的UVa1635的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。