HDU 5175

我想了很久了，后来还是把N分解质因数，枚举各种组合，反正也不多吧，按题目条件，然后就过了。

#include <cstdio> 
#include <iostream> 
#include <cstring>  
#include <cctype>  
#include <algorithm>  
#define LL __int64
using namespace std; 

LL prime[100010],np;
int fac[100010],nf;
int cnt,nop;
struct Node{
	LL f;
	int cnt;
}node[100100];
LL ans[100010];

void predo(LL n){
	np=0;
	bool isprime[100010];
	memset(isprime,false,sizeof(isprime));
	for(LL i=2;i<=n;i++){
		if(!isprime[i]){
			isprime[i]=true;
			prime[np++]=i;
			for(LL j=i*i;j<=n;j+=i)
			isprime[j]=true;
		}
	}
}

bool Isprime(LL n){
	nf=0;
	for(LL i=0;i<np&&prime[i]<=n;i++){
		if(n%prime[i]==0){
			while(n%prime[i]==0){
				fac[nf++]=prime[i];
				n/=prime[i];
			}
		}
	}
	if(n!=1){
		fac[nf++]=n;
	}
	if(nf<=1) return true;
	return false;
}

LL GCD(LL a,LL b){
	if(b==0) return a;
	return GCD(b,a%b);
}

void dfs(LL n,int pos,LL gcd){
	if(pos==nop+1){
		LL x=n^gcd;
		if(x>=n) return ;
		if(x==0) return ;
		if(gcd==GCD(n,x))
		ans[cnt++]=x;
		return ;
	}
	for(int i=0;i<=node[pos].cnt;i++){
		if(i==0){
			dfs(n,pos+1,gcd);
		}
		else{
			gcd*=node[pos].f; 
			dfs(n,pos+1,gcd);
		}
	}
}

int main(){
	int t=0;
	LL n;
	predo(100010LL);
	while(scanf("%I64d",&n)!=EOF){
		if(n==1LL||n==2){
			printf("Case #%d:
",++t);
			puts("0");
			puts("");
			continue;	
		}
		if(Isprime(n)){
			printf("Case #%d:
",++t);
			puts("1");
			printf("%I64d
",n-1);
		}
		else{
			nop=-1;
			for(int i=0;i<nf;i++){
				if(i==0||fac[i]!=fac[i-1]){
					node[++nop].f=fac[i];
					node[nop].cnt=1;
				}
				else
				node[nop].cnt++;
			}

			cnt=0;
			dfs(n,0,1LL);
			sort(ans,ans+cnt);
			printf("Case #%d:
",++t);
			printf("%d
",cnt);
			if(cnt==0){
				puts("");
				continue;
			}
			printf("%I64d",ans[0]);
			for(int i=1;i<cnt;i++){
				printf(" %I64d",ans[i]);
			}
			printf("
");
		}
	}
	return 0;
}