跳蚤问题.txt.txt

关于跳蚤问题的一个小算法

#include<stdio.h>
#include<math.h>
long int n,m;
long int get[100];
int max = 1000;
int que[100];
int total=0;
struct Num
{
	int dig[1000];
	int len;
};
struct Num Z;
void highmul(struct Num &A,struct Num B)
{
	long int i,j,k;
	struct Num C;
	for (i = 0; i < max; i++)
	  C.dig[i] = 0;
	for (i=0;i<A.len;i++)
	  for (j=0;j<B.len;j++)
		 C.dig[i+j] += A.dig[i] * B.dig[j];
	C.len = A.len + B.len - 1;
	k = 0;
	for (i=0;i<C.len;i++)
	  {
		j =  C.dig[i] + k;
		k = j / 10;
		C.dig[i] =j -  k * 10;
	  }
	while (k > 0)
	  {
		C.len++;
		C.dig[i] = k % 10;
		k = k / 10;
		i++;
	  }
	A = C;
}

void highplus(struct Num &A,struct Num B)
{
	long int i,j,k;
	k = (A.len > B.len) ? A.len : B.len;
	j = 0;
	for (i=0;i<k;i++)
	  {
		A.dig[i] += B.dig[i] + j;
		j = A.dig[i] / 10;
		A.dig[i] -= j * 10;
	  }
	while (j > 0)
	  {
		A.len++;
		i++;
		A.dig[i] = j % 10;
		j = j / 10;
	  }
}

void highminus(struct Num &A,struct Num B)
{
	int i,j,k;
	j = 0;
	for (i=0;i<A.len;i++)
	  {
		A.dig[i] -= B.dig[i] + j;
		j = 0;
		if (A.dig[i] < 0) {
			A.dig[i] += 10;
			j = 1;
		};
	  }
	i--;
	while (A.dig[i] == 0 && A.len > 1)
		{
			i--;
			A.len--;
		}
}

void prime()
{
	long int i,j,k;
	long int l=m;
	for (i = 2;i <= sqrt(m); i++)
	  {
		k = 0;
		for (j = 2; j <= sqrt(i); j++)
		  if (i % j == 0) { k = 1; break; }
		if (k == 1) continue;
		if (l % i == 0) {
			total++;
			get[total] = i;
			while (l % i == 0) l = l / i;
		}
	  }
	if (l > 1) {
		total++;
		get[total] = l;
	}
}

void chushi(struct Num &A,long int x)
{
	int i,j;
	for ( i = 0; i < max; i++)
		A.dig[i] = 0;
	A.len = 1;
	A.dig[0] = x % 10;
	x = x / 10;
	i = 0;
	while (x > 0)
	  {
		A.len++;
		i++;
		A.dig[i] = x % 10;
		x = x / 10;
	  }
}

void calc(int now,int dep,int las,int sta)
{
	long int i,j,h;
	struct Num X;
	struct Num Y;
	if (now > dep) {
		j = 1;
		for (i = 1; i <= dep ; i++)
			j *= get[que[i]];
		h = m / j;
		chushi(X,h);
		chushi(Y,1);
		for ( i = 1; i <= n ; i++)
		  highmul(Y,X);
		if (sta == -1) highminus(Z,Y);
		else highplus(Z,Y);
		return ;
	}
	for (i = las + 1; i <= total; i++)
		{
			que[now] = i;
			calc(now + 1, dep, i, sta);
		}
}

void rongchi()
{
	int i,k;
	k = -1;
	for (i = 1; i <= total; i++)
	  {
		calc(1,i,0,k);
		k *= -1;
	  }
}

main()
{
	int i;
	struct Num Y;
	scanf("%ld%ld",&n,&m);
	chushi(Y,m);
	chushi(Z,1);
	for (i = 1; i <= n; i++)
	  highmul(Z,Y);
	prime();
	rongchi();
	for (i = Z.len - 1; i >= 0; i--)
	  printf("%d",Z.dig[i]);
	printf("\n");
	return 0;
}