uva1635

时间:2022-02-10 00:37:23
            /*  哑元  组合数的递推整除判断_________________________________________________________________________________

                #include <iostream>
#include <map>
#include <cmath>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
#define fir first
#define sec second
#define pb(x) push_back(x)
#define mem(A, X) memset(A, X, sizeof A)
#define REP(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define rep(i,l,u) for(int (i)=(int)(l);(i)>=(int)(u);--(i))
#define foreach(e,x) for(__typeof(x.begin()) e=x.begin();e!=x.end();++e)
typedef int LL;
typedef unsigned long long ull;
typedef pair<long,long> pll; LL T,n;
const int mod=1e9+7;
const int maxn=1e5+10; void pre(LL mm,vector <LL> & mf,map<LL,LL> &fp)//prime_resolve ( mm>=1 )mf m_factor, fp factor_power put all the 素因子(即素数)2 ... of m to the factor,且在factor按照从小到大存储.
{
mf.clear(); fp.clear();
if(mm==1) {mf.pb(1); fp[1]=1;}
else
{
for(int i=2;i*i<=mm;i++)
{
if(mm%i==0)
{
mf.push_back(i);
while(mm%i==0) //除干净某个因子.
{
mm/=i;
fp[i]++;
}
}
}
if(mm!=1)
{
mf.push_back(mm); //如果m 是素数 放进去
fp[mm]++;
}
}
} int main()
{
freopen("in.txt","r",stdin);
//while(cin>>n)
int n,m;
while(cin>>n>>m)
{
vector<int> ans;
if(m==1)
{ REP(i,1,n) ans.pb(i);}
else
{
//REP(kase,1,T) { }
vector<int> dm;
map<int ,int > pm;
pre(m,dm,pm); vector<int> curd;
map<int,int > curp;
REP(i,1,(n+1)/2)
{
vector<int> td; map<int,int>tp; if(i==1) {td.pb(1);tp[1]=1;}
else
{ pre(n-i+1,td,tp); vector<int> tempd; map<int,int> tempp;
pre(i-1,tempd,tempp);
REP(j,0,tempd.size()-1)
{
int key=tempd[j];
tp[key]-=tempp[key];
} } map<int,int> ::iterator it;
for(it=tp.begin();it!=tp.end();it++)
curp[it->fir]+=it->sec;
int ok=1; for(it=pm.begin();it!=pm.end();it++)
{
//cout << "-----"<<it->first << endl;
if(it->sec>curp[it->fir]){
//cout<<"i:"<<i<<endl;
ok=0;break;}//
}
if(ok)
{
//cout<<"i :"<<i<<endl;
ans.pb(i);
if(i!=n-i+1) ans.pb(n-i+1);
}
}
sort(ans.begin(),ans.end());
} cout<<ans.size()<<"\n";
if(!ans.empty())
{
cout<<ans[0];
REP(j,1,ans.size()-1) cout<<" "<<ans[j]; }
cout<<"\n";
}
return 0;
} /*
note : 组合数的大数字整除递推 C(n,k)=C(n,k-1)(n-k+1)/k,如果递推式没有除法可以直接进行余数的递推,但是这个里面的递推式中的分母是k,模是某个值m,
而k,m不一定互素,所以不一定可逆。但是极端的去想:如果给的m是一个素数的话可以利用这个性质推出2 到 k-1项。
debug : pe了好几次 最后是当没有哑元的时候也要输出一个空行。
optimize:
*/

相关文章