poj1091(容斥原理+质因子分解)跳蚤

2017年07月24日 8点热度 0人点赞 0条评论
跳蚤
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 10520   Accepted: 3247

Description

Z城市居住着很多只跳蚤。在Z城市周六生活频道有一个娱乐节目。一只跳蚤将被请上一个高空钢丝的正中央。钢丝很长,可以看作是无限长。节目主持人会给该跳蚤发一张卡片。卡片上写有N+1个自然数。其中最后一个是M,而前N个数都不超过M,卡片上允许有相同的数字。跳蚤每次可以从卡片上任意选择一个自然数S,然后向左,或向右跳S个单位长度。而他最终的任务是跳到距离他左边一个单位长度的地方,并捡起位于那里的礼物。 
比如当N=2,M=18时,持有卡片(10, 15, 18)的跳蚤,就可以完成任务:他可以先向左跳10个单位长度,然后再连向左跳3次,每次15个单位长度,最后再向右连跳3次,每次18个单位长度。而持有卡片(12, 15, 18)的跳蚤,则怎么也不可能跳到距他左边一个单位长度的地方。 
当确定N和M后,显然一共有M^N张不同的卡片。现在的问题是,在这所有的卡片中,有多少张可以完成任务。 

Input

两个整数N和M(N <= 15 , M <= 100000000)。

Output

可以完成任务的卡片数。

Sample Input

2 4

Sample Output

12

Hint

这12张卡片分别是: 
(1, 1, 4), (1, 2, 4), (1, 3, 4), (1, 4, 4), (2, 1, 4), (2, 3, 4), 
(3, 1, 4), (3, 2, 4), (3, 3, 4), (3, 4, 4), (4, 1, 4), (4, 3, 4) 
/*容斥原理+质因子分解 ,请选择g++编译器,不然编译错误 
我们假设卡片上的标号分别是a1,a2,...,an,M,
跳蚤跳对应标号的卡片的次数分别为x1,x2,...,xn,xn+1,
那么要满足已知条件只需满足方程a1*x1+a2*x2+...+an*xn+M*xn+1=1有解,
即gcd(a1,a2,...,an,m)=1, 于是只要a1...n中一起有个m的公因子即可 
*/
//数据还是蛮水的,不需要用到大数 
#include
#include
#include
#include
using namespace std;
#define ll long long
int n,m;
vector x;
void getprime(int m)
{
	//得到m的质因子
	x.clear();
	for(int i=2;i*i<=m;++i)
	if(m%i==0)
	{
		x.push_back(i);
		while(m%i==0) m/=i;
	}
	if(m!=1) x.push_back(m);
}
int main(){
	while(~scanf("%d%d",&n,&m))
	{
		getprime(m);
		ll ans=pow(m,n);
		for(int i=1;i<(1<
未经允许不得转载!poj1091(容斥原理+质因子分解)跳蚤

update

纸上得来终觉浅, 绝知此事须躬行。