记录编号	151930	评测结果	AAAAAAAAAA
题目名称	亲和数	最终得分	100
用户昵称	TA	是否通过	通过
代码语言	C++	运行时间	0.083 s
提交时间	2015-03-11 21:12:30	内存使用	0.70 MiB

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAXN 10000
int prime[100000];
#include<bitset>
#include<iostream>
bitset<MAXN> p;
typedef long long LL;
int work(int x){
	LL ans=1;
	int sum,X=x;
	for(int i=1;i<prime[0]&&ans&&prime[i]*prime[i]<=x;++i)
		if(x%prime[i]==0){
			sum=1;
			for(;x%prime[i]==0;x/=prime[i])sum*=prime[i];
			ans*=((LL)prime[i]*sum-1)/(prime[i]-1);
			if(ans>1E9)ans=0;
		}
	if(x!=1){
		ans*=(x+1);
		if(ans>1E9)ans=0;
	}
	return ans-X;
}
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,ans,Ans=0;
	scanf("%d%d",&A,&B);
	for(j=A;j<=B;++j){
		ans=work(j);
		if(ans>j&&work(ans)==j)++Ans;
	}
	printf("%d\n",Ans);
}