Facebook Hacker Cup 2015 Round 1 Homework

Facebook Hacker Cup 2015 Round 1 Homework（附带测试数据） - 脑残的孩子只有慢慢学。。 - 博客频道 - CSDN.NET

Your first-grade math teacher, Mr. Book, has just introduced you to an amazing new concept ― primes! According to your notes, a prime is a positive integer greater than 1 that is divisible by only 1 and itself.

Primes seem fun, but without giving you and your 6-year-old colleagues time to consider their implications, he's promptly gone on to define another term: primacity. He explains that the primacity of an integer is the number of distinct primes which divide it. For example, the primacity of 12 is 2 (as it's divisible by primes 2 and 3), the primacity of 550 is 3 (as it's divisible by primes 2, 5, and 11), and the primacity of 7 is 1 (as the only prime it's divisible by is 7).

Following his lesson, Mr. Book has given you homework with some rather mean questions of the following form: Given 3 integers A, B, and K, how many integers in the inclusive range [A, B] have a primacity of exactly K?

Mr. Book probably expects his little homework assignment to take you and your classmates the rest of the year to complete, giving him time to slack off and nap during the remaining math classes. However, you want to learn more things from him instead! Can you use the skills you've learned in your first-grade computer science classes to finish Mr. Book's homework before tomorrow's math class?

Input

Input begins with an integer T, the number of homework questions. For each question, there is one line containing 3 space-separated integers: A, B, and K.

Output

For the ith question, print a line containing "Case #i: " followed by the number of integers in the inclusive range [A, B] with a primacity of K.

Constraints

1 ≤ T ≤ 100
2 ≤ A ≤ B ≤ 10⁷
1 ≤ K ≤ 10⁹

Explanation of Sample

In the first test case, the numbers in the inclusive range [5, 15] with primacity 2 are 6, 10, 12, 14, and 15. All other numbers in this range have primacity 1.

Example input ・

Example output ・        

5  5 15 2  2 10 1  24 42 3  1000000 1000000 1  1000000 1000000 2  

Case #1: 5  Case #2: 7  Case #3: 2  Case #4: 0  Case #5: 1

给一个区间，求该区间内 质因子个数等于k的数 的个数。

http://www.myexception.cn/program/1827018.html

这个题很水，打个表就过了。这个表记录的是某个数有多少个质因数。表的处理方式类似于筛素数。
https://github.com/gshopov/competitive-programming-archive/blob/master/dmoj/facebook-hacker-cup/2015/round-1/homework.cpp

	vector<vector<unsigned int>> group_by_primacity(unsigned int up_to) {
	vector<unsigned int> primacity(up_to + 1);
	for (unsigned int i {2}; i <= up_to; ++i)
	{
	if (!primacity[i])
	{
	primacity[i] = 1;
	for (unsigned int j {2 * i}; j <= up_to; j += i)
	{
	++primacity[j];
	}
	}
	}
	vector<vector<unsigned int>> by_primacity(9);
	for (unsigned int i {0}; i <= up_to; ++i)
	{
	by_primacity[primacity[i]].push_back(i);
	}
	return by_primacity;
	}
	int main()
	{
	use_io_optimizations();
	auto by_primacity = group_by_primacity(upper_limit);
	unsigned int test_cases;
	cin >> test_cases;
	for (unsigned int test {1}; test <= test_cases; ++test)
	{
	unsigned int lower;
	unsigned int upper;
	unsigned int primacity;
	cin >> lower >> upper >> primacity;
	cout << "Case #" << test << ": "
	<< upper_bound(by_primacity[primacity].cbegin(),
	by_primacity[primacity].cend(),
	upper) -
	lower_bound(by_primacity[primacity].cbegin(),
	by_primacity[primacity].cend(),
	lower)
	<< '\n';
	}
	return 0;
	}

https://github.com/ChenXinyue/AlgorithmPractices/blob/master/CodeForces/2015%20Facebook%20Hacker%20Cup,%20Round%201-A-Homework.java

	int[] record = new int[10000005];
	public void init() {
	Arrays.fill(record, 0);
	for (int i = 2; i <= 10000000; i++) {
	if (record[i] > 0) {
	continue;
	}
	for(int j = i; j <= 10000000; j += i){
	record[j]++;
	}
	}
	Scanner scan = new Scanner(System.in);
	int count = scan.nextInt();
	for (int i = 0; i < count; i++) {
	int startIndex = scan.nextInt();
	int endIndex = scan.nextInt();
	int k = scan.nextInt();
	int result = 0;
	for (int j = startIndex; j <= endIndex; j++) {
	if (record[j] == k) {
	result++;
	}
	}
	System.out.println("Case #" + (i + 1) + ": " + result);
	}
	scan.close();
	}

1. int f[M];  
2. void pri()  
3. {  
4.     int t = 0;  
5.     for(int i = 2; i <= M; i++)  
6.     {  
7.        if(!f[i])  
8.        {  
9.            f[i]++;  
10.            for(int j=2;i*j<=M;j++)  
11.            {  
12.                f[i*j]++;  
13.            }  
14.        }  
15.        //printf("%d %d\n",f[i] ,i);  
16.     }  
17.   
18. }  
19.   
20. int main()  
21. {  
22.     //freopen("data.txt","w",stdout);  
23.     pri();  
24.     int t,case1=1;  
25.     while(scanf("%d",&t)!=EOF)  
26.     {  
27.         while(t--)  
28.         {  
29.             int a,b,k,ans;  
30.             scanf("%d%d%d",&a,&b,&k);  
31.             ans=0;  
32.             for(int i=a;i<=b;i++)  
33.             {  
34.                 if(f[i]==k)ans++;  
35.             }  
36.             printf("Case #%d: %d\n",case1++,ans);  
37.         }  
38.     }  
39.     return 0;  
40. } 

Read full article from Facebook Hacker Cup 2015 Round 1 Homework（附带测试数据） - 脑残的孩子只有慢慢学。。 - 博客频道 - CSDN.NET