首页 > ACM题库 > HDU-杭电 > hdu 2284 Solve the puzzle, Save the world!-数论-[解题报告]C++
2014
01-05

hdu 2284 Solve the puzzle, Save the world!-数论-[解题报告]C++

Solve the puzzle, Save the world!

问题描述 :

In the popular TV series Heroes, there is a tagline "Save the cheerleader, Save the world!". Here Heroes continues, "Solve the puzzle, Save the world!".
Finally, alien invaders visit our planet. They are eccentric and launch attack many rounds. Since trust in prime numbers, each round they send out p killers, here p is a prime number. Countries on our planet unite and assemble an armed troop of n population. And fortunately we get a fatal weakness of enemy from a betrayer. If the ways of choosing m warriors from n is a multiple of p, the killer number, we will win. Otherwise, we will lose. As the greatest programmer of our planet, you are invited to write a program to count the number of m(0≤m≤n) such that C(n, m) is a multiple of prime p.

输入:

Each line will contain an integer n(1≤n≤10^5) and a prime p(2≤p<10^7), separated by a single space. Process to the end of file.

输出:

Each line will contain an integer n(1≤n≤10^5) and a prime p(2≤p<10^7), separated by a single space. Process to the end of file.

样例输入:

6 2
5333 127
100000 11

样例输出:

3
Where is hero from?
92301

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2284

题意:外星人派出p个杀手(p为素数),地球人从n个人中选出m个组成军队,如果从n中选出m个人的选法是p的倍数就赢,问有多少种赢的方法。

思路:详见代码,代码中提到的剪枝方法参考自这里:http://blog.csdn.net/ice_crazy/article/details/8607180,不剪枝会慢10几ms。

这样剪枝的原因:因为p为素数,那么它和它的倍数不可能被比它小的数相乘得到。

P.S.这个题怎么过的人那么少……

#include <cstdio>

int main ()
{
	int n,p;
	while (~scanf("%d%d",&n,&p))
	{
		if (n==0 || p>n)        //这个剪枝是从网上学的
		{
			printf("Where is hero from?\n");
			continue;
		}
		int cnt=0,ans=0;
		for (int m=1;m<=n/2;m++)
		{
			int temp=n-m+1;
			while (temp%p==0)
				cnt++,temp/=p;   //分子中有几个p因子
			temp=m;
			while (temp%p==0)
				cnt--,temp/=p;   //分母中有几个p因子
			if (cnt<=0)        //只有分子p因子的个数多余分母时才能整除p
				continue;
			if (2*m == n)    //m为n(n为偶数)的一半
				ans++;
			else
				ans+=2;     //m和n-m的组合数一样
		}
		if (ans)
			printf("%d\n",ans);
		else
			printf("Where is hero from?\n");
	}
	return 0;
}

解题转自:http://blog.csdn.net/whyorwhnt/article/details/8675540


  1. 第一题是不是可以这样想,生了n孩子的家庭等价于n个家庭各生了一个1个孩子,这样最后男女的比例还是1:1

  2. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。

  3. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  4. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。