例题 10-6 无关的元素（Irrelevant Elements, ACM/ICPC NEERC 2004, UVa1635）

本文主要是介绍例题 10-6 无关的元素（Irrelevant Elements, ACM/ICPC NEERC 2004, UVa1635），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：https://vjudge.net/problem/UVA-1635
分类：基础数论
备注：唯一分解定理，递推

一开始想对每个数求出质因子的指数，然后看能不能符合条件，发现会T。看了下别人的，原来是对m的每个质因子进行判断。最近可能退步了许多，只会想暴力，应该要多换换角度来看问题，不能一根筋。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxm=1e9;
const int maxl=1e5+5;
ll n,m;
int prime[maxl],tot,vis[maxl],has[maxl],ans[maxl];
bool tag[maxl],kase;
void init(){int k=sqrt(maxm+0.5);for(int i=2;i<=k;i++)if(!vis[i]){prime[tot++]=i;for(int j=i*i;j<=n;j+=i)vis[j]=1;}
}int main(void){// freopen("in.txt","r",stdin);// freopen("out.txt","w",stdout);init();while(~scanf("%lld%lld",&n,&m)){int cnt=0,x=m;for(int i=0;i<tot;i++){if(m%prime[i]==0){has[cnt++]=prime[i];while(m%prime[i]==0)m/=prime[i];}if(m==1)break;}if(m>1)has[cnt++]=m;memset(tag,0,sizeof(tag));for(int i=0;i<cnt;i++){int t=x;int me=0, pe=0;while(t%has[i]==0){t/=has[i];me++;}//C(k,n)=(n-k+1)/k*C(k-1,n)//C(k,n-1)=(n-k)/k*C(k-1,n-1)//C(k,n-1)是第k+1个数的系数for(int k=1;k<n;k++){int up=n-k;while(up%has[i]==0){up/=has[i];pe++;}int down=k;while(down%has[i]==0){down/=has[i];pe--;}if(pe<me)tag[k+1]=1;}}tag[1]=1;int ansNum=0;for(int i=1;i<=n;i++)if(!tag[i])ans[ansNum++]=i;printf("%d\n",ansNum);for(int i=0;i<ansNum;i++)printf("%d%c",ans[i],(i==ansNum-1)?'\n':' ');if(!ansNum)printf("\n");}return 0;
}