记录编号	48382	评测结果	AAAAAAAAAA
题目名称	整数合并	最终得分	100
用户昵称	Eme丶	是否通过	通过
代码语言	C++	运行时间	0.022 s
提交时间	2012-11-05 17:19:20	内存使用	4.39 MiB

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#define N 100010
using namespace std;

int tot,l,r,p;
int f[N],a[N],g[N];
bool b[N]; 


void Init()
{
	scanf("%d%d%d",&l,&r,&p);
	a[0]=0;
	b[2]=true;
	memset(b,true,sizeof b);
	for (int i=2;i<=r;i++)
	{
		if (b[i]  &&  i>=p) a[++a[0]]=i;
		if (b[i])
		{
			for (int j=1;j*i<=r;j++) b[j*i]=false;
		}
	}
}

int Get(int x)
{
	if (x==f[x]) return x;
	f[x]=Get(f[x]);
	return f[x];
}

void Union(int x,int y)
{
	int fx=Get(x);
	int fy=Get(y);
	if (fx!=fy)
	{
		f[fx]=fy;
		g[fy]+=g[fx];
		tot--;
	}
}

void Main()
{
	for (int i=1;i<=r;i++) f[i]=i;
	for (int i=1;i<=r;i++) g[i]=1;
	tot=r-l+1;
	for (int i=1;i<=a[0];i++)
	{
		int lb=(l/a[i]);
		if (l % a[i]!=0) lb++;
		int rb=(r/a[i])-1;
		for (int j=lb;j<=rb;j++) Union(a[i]*j,a[i]*(j+1));
	}
	printf("%d\n",tot);
}

int main()
{
	freopen("setb.in","r",stdin);
	freopen("setb.out","w",stdout);
	
	Init();
	Main();
		
	fclose(stdin); fclose(stdout);
	return 0;
}