记录编号	151912	评测结果	AAAAAAAAAA
题目名称	371.亲和数	最终得分	100
用户昵称	TA	是否通过	通过
代码语言	C++	运行时间	0.168 s
提交时间	2015-03-11 20:00:01	内存使用	38.46 MiB

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAXN 10000
int prime[10000000];
#include<bitset>
#include<iostream>
bitset<MAXN> p;
int pri[30],sum[30],tot,T;
typedef long long LL;
void dfs(int x,int now){
	if(x==tot){
		if(T>-1E9){
			T+=now;
			//cout<<now<<" ";
			if(T>1E8)T=-1E9;
		}
		return;
	}
	dfs(x+1,now);
	for(int i=sum[x];i--;)dfs(x+1,now*=pri[x]);
}
int work(int x){
	tot=0,T=-x;
	//cout<<x<<":";
	for(int i=1;i<prime[0]&&prime[i]*prime[i]<=x;++i)
		if(x%prime[i]==0){
			pri[tot]=prime[i],sum[tot]=0;
			for(;x%prime[i]==0;x/=prime[i])++sum[tot];
			++tot;
		}
	if(x!=1)pri[tot]=x,sum[tot++]=1;
	dfs(0,1);
	//cout<<"->"<<T<<endl;
	return T;
}
int main(){
	freopen("amicable.in","r",stdin);
	freopen("amicable.out","w",stdout);
	int i,j;
	prime[0]=1;
	for(i=2,j;i<MAXN;++i){
		if(~p[i])prime[prime[0]++]=i;
		for(j=1;j<prime[0]&&i*prime[j]<MAXN;++j){
			p[i*prime[j]]=1;
			if(i%prime[j]==0)break;
		}
	}
	int A,B,x,ans,Ans=0;
	scanf("%d%d",&A,&B);
	for(j=A;j<=B;++j){
		//cout<<"-------"<<j<<"---------\n";
		ans=work(j);
		if(ans>j&&work(ans)==j)++Ans;
	}
	printf("%d\n",Ans);
}