2014
01-05

# 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

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;
}

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

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

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

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