首页 > 代码库 > 数论 - 组合数学 + 素数分解 --- hdu 2284 : Solve the puzzle, Save the world!
数论 - 组合数学 + 素数分解 --- hdu 2284 : Solve the puzzle, Save the world!
Solve the puzzle, Save the world!
Problem Description
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.
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.
Input
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.
Output
For each test of case, if the world can be saved, output the number of ways, otherwise, output "Where is hero from?"(without quotation), both on a single line.
Sample Input
6 25333 127100000 11
Sample Output
3Where is hero from?92301
Mean:
给你两个数n和p,现在要你从n中选出m个数，如果n取m能够被p整除，那么为可行方案，问可行方案数有多少种。
analyse:
如果数据小的话确实是道水题，当然只要想到这个方法，一样也是水题。
如果我们用传统的方法：枚举m，然后求c(n,m)，再看能不能被p整除这样暴力来做的话，光是c(n,m)就存不下，更别提判断整除了。
这题用了一个巧妙的方法，由于题目说p是一个素数，那么我们可直接来统计c(n,m)分子分母的素因子，然后相减之后就是c(n,m)的p因子了。
Time complexity：O(n)
Source code：
// Memory Time// 1347K 0MS// by : Snarl_jsb// 2014-09-09-20.25#include<algorithm>#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#include<vector>#include<queue>#include<stack>#include<map>#include<string>#include<climits>#include<cmath>#define N 1000010#define LL long longusing namespace std;int main(){// freopen("C:\\Users\\ASUS\\Desktop\\cin.cpp","r",stdin);// freopen("C:\\Users\\ASUS\\Desktop\\cout.cpp","w",stdout); long long n,p; while(~scanf("%I64d %I64d",&n,&p)) { if(!n||p>n) { puts("Where is hero from?"); continue; } long long tmp,cnt,m,ans; ans=cnt=0; for(m=1;m<=n/2;m++) { tmp=n-m+1; while(!(tmp%p)) { cnt++; tmp/=p; } tmp=m; while(!(tmp%p)) { cnt--; tmp/=p; } if(cnt<=0) continue; if(m*2==n) ans++; else ans+=2; } if(ans) cout<<ans<<endl; else puts("Where is hero from?"); } return 0;}
数论 - 组合数学 + 素数分解 --- hdu 2284 : Solve the puzzle, Save the world!
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。