记录编号	23131	评测结果	AAAAAAAAAA
题目名称	八	最终得分	100
用户昵称	Pom	是否通过	通过
代码语言	C++	运行时间	0.296 s
提交时间	2011-03-01 09:57:29	内存使用	1.64 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;

long long a,b,n,sum,shu[16],i,j,k,s,ci[16],MAX;
long long now[10001],su[10001],tot,fen[16][10001];
bool B[10001];

long long calc(long long key)
{
	return b/key-(a-1)/key;
}

long long POW(long long di,long long ci)
{
	long long re=1;
	for (int j=1;j<=ci;j++)
		re*=di;
	return re;
}

void pd()
{
	long long re=1;
	if (now[1]<3) now[1]=3;
	for (k=1;k<=tot;k++)
	{
		re*=POW(su[k],now[k]);
		if (re>b) return;
	}
	if (i%2==0) sum+=calc(re);
	else sum-=calc(re);
}

void dfs(long long start)
{
	long long k;
	if (s==i)
	{
		pd();
		return;
	}
	long long re[10001];
	for (k=1;k<=tot;k++)
		re[k]=now[k];
	for (k=start;k<=n-i+s+1;k++)
	{
		for (int j=1;j<=tot;j++)
			if (now[j]<fen[k][j]) now[j]=fen[k][j];
		++s;
		dfs(k+1);
		--s;
		for (int j=1;j<=tot;j++)
			now[j]=re[j];
	}
}

int main()
{	
	freopen("eight.in","r",stdin);
	freopen("eight.out","w",stdout);
	scanf("%d",&n);
	for (i=1;i<=n;i++)
	{
		scanf("%d",&shu[i]);
		if (!8%shu[i])
		{
			printf("0\n");
			return 0;
		}
	}
	//筛素数
	B[1]=false;
	for (i=2;i<=10000;i++)
		if (!B[i])
		{
			j=i;
			su[++tot]=i;
			while (j<=10000)
			{
				B[j]=true;
				j+=i;
			}
		}
	//分解各数
	for (i=1;i<=n;i++)
	{
		for (j=1;j<=tot;j++)
			while (shu[i]%su[j]==0)
			{
				fen[i][j]++;
				shu[i]/=su[j];
			}
	}
	scanf("%d%d",&a,&b);
	sum=calc(8);
	for (i=1;i<=n;i++)
	{
		memset(now,0,sizeof(now));
		MAX=0;
		s=0;
		int re=sum;
		dfs(1);
		if (re==sum) break;
	}
	printf("%d\n",sum);
	return 0;
}