记录编号	23049	评测结果	AAATTAATTT
题目名称	最多因子数	最终得分	50
用户昵称	苏轼	是否通过	未通过
代码语言	C++	运行时间	5.338 s
提交时间	2011-02-24 11:40:03	内存使用	0.29 MiB

#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>

using namespace std;

int p[4000], dv[4000];

void gen_prime (int *l, const int n)
{
	int *p = l++;
	bool fl;

	*p++ = 2;
	for (int i=3;  i<=n;  i+=2)
	{
		fl = true;
		for (int *j=l;  j!=p;  j++)
			if (! (i%*j))
			{
				fl = false;
				break;
			}

		if (fl)
			*p++ = i;
	}
	*p = 0x7FFFFFFF;
}

int main (void)
{
	ifstream fin("divisors.in");
	ofstream fout("divisors.out");

	int l, u;
	fin >> l >> u;
	vector<bool> test;
	test.resize(u-l+1);
	gen_prime(p, (int)sqrt(u));

	int i, tmp, pcp=0, count, *it, maxd=0, maxp=0;
	for (int i=u;  i>=l;  i--)
		if (!test[i-l])
		{
			count = 1;
			tmp = i;
			it = p;
			pcp = 0;

			while (tmp >= *it)
				if (tmp % *it == 0)
				{
					tmp /= *it;
					pcp++;
					if (tmp-l>=0)
						test[tmp-l] = 1;
				}
				else
				{
					count *= pcp+1;
					pcp = 0;
					it++;
				}

			count *= pcp+1;
			if (tmp != 1)
				count *= 2;
			if (count >= maxd)
			{
				maxd = count;
				maxp = i;
			}
		}

	fout << "Between " << l << " and "<< u <<
			", " << maxp << " has a maximum of "
			<< maxd << " divisors." << endl;

	fin.close();
	fout.close();

	return 0;
}