算法

POJ1091总结

跳蚤

题目来源

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)

我的代码

题目意思是求满足使得a1X1+a2X2+……..+anXn+an+1Xn+1=1a1X1+a2X2+……..+anXn+an+1Xn+1=1有解的序列的个数,也就是这n+1个数的最大公约数是1,证明过程

将所有序列中不满足条件的序列删去,剩下的就是符合条件的了。由于已经确定第n+1个数是m且其它数小于等于m,那么如果要有公约数,必须是m的因子,且这个公约数由m的质因子构成,那么就可以将所有以m的质因子构成的因子为最大公约数的序列删去即可。

假设当前求以x为最大公约数的序列个数,以x为因子的数一共有m/x个,根据乘法原理,这样的序列有(m/x)^n个。

所以只要求由k个质因子构成的数为最大公约数的序列的个数就好,然后根据容斥原理,做好加减就行。

#include<stdio.h>

long long n,m,sum,ans;
int cnt=0;
int p[1000],tempP[1000];
void getP(long long m)
{
	int tempm=m;
	for (long long i=2;i*i<=m;i++)
	{
		if(tempm%i==0) p[cnt++]=i;
		while (tempm%i==0)
		{
			tempm=tempm/i;
		}
	}
	if (tempm>1) p[cnt++]=tempm;
}
long long quick(long long n,long long m)
{
	long long num=1;
	while(m!=0)
	{
		
		if(m&1) num=num*n;
		n=n*n;
		m>>=1;
	}
	return num;
}
void dfs(int nowP,int step,int num)
{
	
	if (step==num)
	{
		long long tempm=m;
		for (int i=0;i<num;i++) tempm=tempm/tempP[i];
		sum+=quick(tempm,n);
		return;
	}
	else
	{
		for (int i=nowP;i<cnt;i++)
		{
			tempP[step]=p[i];
			dfs(i+1,step+1,num);
		}
	}
	return ;
}
int main()
{
	while (scanf("%d%d",&n,&m)!=EOF)
	{
		cnt=0;
		getP(m);
		ans=quick(m,n);
		for (int i=1;i<=cnt;i++)
		{
			sum=0;
			dfs(0,0,i);
			if (i&1) ans=ans-sum;
			else ans=ans+sum;
			
		}
		printf("%lld\n",ans);
	}
	return 0;
}

反思

数论不会。

发表评论