【数论+容斥】POJ 1091 跳蚤_C/C++_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > C/C++ > 【数论+容斥】POJ 1091 跳蚤

【数论+容斥】POJ 1091 跳蚤

 2012/6/11 0:14:38  基德KID.1412  程序员俱乐部  我要评论(0)
  • 摘要:KIDx的解题报告题目链接:http://poj.org/problem?id=1091假设卡片上标号分别是a1,a2,...,an,M,跳蚤跳对应号的次数分别为x1,x2,...,xn,跳M个单位长度的次数是xn+1,那么要满足已知条件只需满足方程:a1x1+a2x2+...+anxn+Mxn+1=1有解,即:gcd(a1,a2,...,an,M)=1,接下来对M进行素因子分解,然后排除公因子非1的情况即可。如代码所示:设g为公因子非1的情况数,f(i)表示有i个公因子的情况数,由容斥原理得
  • 标签:

KIDx的解题报告

?

题目链接:http://poj.org/problem?id=1091

?

假设卡片上标号分别是a1, a2, ..., an, M,跳蚤跳对应号的次数分别为x1, x2, ..., xn,跳M个单位长度的次数是xn+1,那么要满足已知条件只需满足方程:

a1x1+a2x2+...+anxn+Mxn+1 = 1 有解,即:

gcd (a1, a2, ..., an, M) = 1,接下来对M进行素因子分解,然后排除公因子非1的情况即可。

?

如代码所示:

设g为公因子非1的情况数,f(i)表示有i个公因子的情况数,由容斥原理得:g = f(1) - f(2) + f(3) -... f(k)

?

#include <iostream>
using namespace std;
#define LL __int64

int fac[35], k, a[20], n, m, x;
LL tp;

LL my_pow (LL a, int b)		//计算a^b
{
	LL res = 1;
	while (b--) res *= a;
	return res;
}

void dfs (int pos, int cnt, int num)	//dfs得到卡片中n+1个数有num个公因子时的方法数
{
	if (cnt == num)
	{
		x = m;
		for (int i = 0; i < cnt; i++)
			x /= a[i];					//x/p表示[1,x]中有多少个数是p的倍数
		tp += my_pow (x, n);			//要选n个数,每个数有x种选择
		return ;
	}
	for (int i = pos; i < k; i++)
	{
		a[cnt] = fac[i];
		dfs (i+1, cnt+1, num);
	}
}

void divide (int p)						//分解素因子,fac存放p的所有素因子
{
	for (int i = 2; i * i <= p; i++)
	{
		if (p % i == 0)
		{
			fac[k++] = i;
			p /= i;
			while (p % i == 0)
				p /= i;
		}
	}
	if (p > 1) fac[k++] = p;
}

int main()
{
	LL ans, g;
	int i;
	while (cin >> n >> m)
	{
		g = 0;
		divide (m);
		for (i = 1; i <= k; i++)			//g = f(1)-f(2)+f(3)-f(4)+...f(k)
		{
			tp = 0;
			dfs (0, 0, i);
			if (i & 1) g += tp;
			else g -= tp;
		}
		ans = my_pow (m, n) - g;		 //ans = m^n - g
		cout << ans << endl;
	}
	return 0;
}

?

  • 相关文章
发表评论
用户名: 匿名