首页 > ACM题库 > HDU-杭电 > hdu 2574 Hdu Girls’ Day-数论-[解题报告]C++
2014
02-10

hdu 2574 Hdu Girls’ Day-数论-[解题报告]C++

Hdu Girls’ Day

问题描述 :

Hdu Girls’ Day is a traditional activity in Hdu. Girls in Hdu participate in the activity and show their talent and skill. The girls who win in the activity will become the Hdu’s vivid ambassadors(形象大使). There are many students in Hdu concern the activity. Now it’s the finally competition to determine who will be the Hdu’s vivid ambassadors. The students vote for the girl they prefer. The girl who has the most number of votes will be the first. You as a student representing Hdu Acm team has a chance to vote. Every girl who participates in the activity has an unique No. and name. Because you very like prime number, you will vote for the girl whose No. has the maximum number of unique prime factors.

For example if the girl’s No. is 12, and another girl’s No. is 210, then you will choose the girl with No. 210. Because 210 = 2 *3 * 5*7 , 12 = 2*2*3. 210 have 4 unique prime factors but 12 just have 2. If there are many results, you will choose the one whose name has minimum lexicographic order.

输入:

The first line contain an integer T (1 <= T <= 100).Then T cases followed. Each case begins with an integer n (1 <= n <= 1000) which is the number of girls.And then followed n lines ,each line contain a string and an integer No.(1 <= No. <= 2^31 – 1). The string is the girl’s name and No. is the girl’s No.The string’s length will not longer than 20.

输出:

The first line contain an integer T (1 <= T <= 100).Then T cases followed. Each case begins with an integer n (1 <= n <= 1000) which is the number of girls.And then followed n lines ,each line contain a string and an integer No.(1 <= No. <= 2^31 – 1). The string is the girl’s name and No. is the girl’s No.The string’s length will not longer than 20.

样例输入:

2
3
Kate 56
Lily 45
Amanda 8
4
Sara 55
Ella 42
Cristina 210
Cozzi 2

样例输出:

Kate
Cristina

#include <iostream>
#include <map>
#include <string>
using namespace std;

int prime[7000];
int cnt;

bool isok (int x)
{
	for (int i = 0; i < cnt && prime[i]*prime[i] <= x; i++)
		if (x % prime[i] == 0) 
			return false;
	return true;
}
void getprime ()
{
	cnt = 2;
	prime[0] = 2;
	prime[1] = 3;
	for (int i = 5; i < 65535; i ++)
		if (isok (i)) prime[cnt++] = i;
}

int divisor (int n)
{
	int count = 0;
	//prime[i]*prime[i] <= n;省了很多时间
	for (int i = 0; i < cnt && prime[i]*prime[i] <= n; i++)
	{
		if (n % prime[i] == 0)
		{
			count ++;
			while (n % prime[i] == 0 && n)
				n /= prime[i];
		}
	}
	//灰常重要 BUG
	if (n > 1) count++;
	return count;
}

int main()
{
	getprime();
	int t;
	cin >> t;
	while(t--)
	{
		map<string, int> m;
		int n; 
		cin >> n;
		string a;
		int num;
		while(n--)
		{
			cin >> a >> num;
			m.insert(pair<string, int>(a, divisor(num)));
		}
		int max = 0;
		string result;
		for(map<string, int>::iterator it = m.begin(); it != m.end(); ++it)
		{
			if(max < it->second)
			{
				max = it->second;
				result = it->first;
			}
		}
		cout << result << endl;
	}
	return 0;
}

解题转自:http://blog.csdn.net/vsooda/article/details/7985271


  1. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥