网站开发软件和工具ide和编辑器,域名不作网站用途,做网站备案要处省的电话号码,网站设计制作要多少钱我们很容易发现最后每一项的系数就是二项式展开#xff0c;余数和m没有关系就意味着可以被m整除#xff0c;因此我们就需要求出每一个二项式的系数。但是数据实在太大我们根据唯一分解定理将m和系数都进行分解#xff0c;然后比较因子的幂。
二项式的计算我们可以根据杨辉三…我们很容易发现最后每一项的系数就是二项式展开余数和m没有关系就意味着可以被m整除因此我们就需要求出每一个二项式的系数。但是数据实在太大我们根据唯一分解定理将m和系数都进行分解然后比较因子的幂。
二项式的计算我们可以根据杨辉三角递推可是这个实在是太大了递推很慢。 所以我们要知道二项式的另一个递推式C(n,k)C(n,k-1)*(n-k1)/k,递推出需要的素数的分解式。
我们发现判断每一个系数是否能够被m整除需要将所有的因子进行比较如果不处理的话109需要105 的素数表每一次都是105的比较这样太耗时了很多操作都是没有意义的因为m根本没有那么多因子。为了优化我们用一个表记录m的所有素因子和每个因子出现的次数然后再用另一个数组记录系数中这些因子出现的次数这样就可以大大提升时间效率。
输出为0的时候要多输出一个换行需要注意。
#includecstdio
#includecstring
#includealgorithm
#includeclimits
#includecctype
#includequeue
#includeset
#includecmathusing namespace std;typedef long long ll;
const int INF0x3f3f3f3f;
const int MAXN1e55;
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()
{tot0;for(int i2;iMAXN;i){if(!check[i]) prime[tot]i;for(int j0;jtot prime[j]*iMAXN ;j){check[prime[j]*i]true;if(i%prime[j]0) break;}}
}bool ok()
{for(int i0;itop;i){if(cnt2[i]tmp[i]) return false;}return true;
}void deal(int x,int d)
{for(int i0;itop;i){while(x%cnt1[i]0){tmp[i]d;x/cnt1[i];}if(x1) break;}
}int first1;int main()
{//freopen(data.out,w,stdout);creat_prime();while(~scanf(%d%d,n,m)){num0; top0;memset(cnt2,0,sizeof(cnt2));for(int i0;itot;i){if(m%prime[i]0){cnt1[top]prime[i];while(m%prime[i]0){cnt2[top];m/prime[i];}top;}if(m1) break;}if(m!1){cnt1[top]m;cnt2[top];top;}memset(tmp,0,sizeof(tmp));for(int i1;in-1;i){deal(n-i,1);deal(i,-1);if(ok()){ans[num]i1;}}
// if(first) first0;
// else printf(\n);printf(%d\n,num);if(num0){printf(\n);continue;}for(int i0;inum-1;i){printf(%d ,ans[i]);}printf(%d\n,ans[num-1]);}return 0;
}
