`

【数论+容斥】POJ 1091 跳蚤

阅读更多

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;
}

 

1
1
分享到:
评论
2 楼 基德KID.1412 2012-05-17  
tenderuser 写道
背包问题 

纳尼?!怎么用背包搞? 
1 楼 tenderuser 2012-05-17  
背包问题 

相关推荐

    hdu 1695 GCD(欧拉函数+容斥原理).docx

    容斥原理是指,在数论中,容斥原理是一种常用的计算技术,用于计算满足某些条件的整数个数。 容斥原理的基本思想是,先计算满足某些条件的整数个数,然后再减去满足其他条件的整数个数,从而得到满足所有条件的整数...

    POJ 新手题目+部分难题 基本数论+图论+组合数学

    2505 2521 2538 2546 2551 2590 2593 2601 2665 2680 2739 2752 2761 2762 2777 2800 2891 2893 2992 3030 3041 3132 3159 3187 3204 3270 3277 3281 3297 3321 3414 3436 3461 3650 3663 3664 3672 3740

    数论讲义+数论pdf.zip

    数论,作为数学的一个分支,主要研究整数的性质,特别是它们之间的关系和结构。它在密码学、编码理论、计算机科学以及纯数学的多个领域都有广泛应用。本资源包含两个文件,分别是“数论.pdf”和“数论讲义+上册.rar...

    ACM常用算法及其相应的练习题.docx

    + poj1860, poj3259, poj1062, poj2253, poj1125, poj2240 * 最小生成树算法:prim, kruskal + poj1789, poj2485, poj1258, poj3026 * 拓扑排序:poj1094 * 二分图的最大匹配:匈牙利算法 + poj3041, poj3020 * ...

    容斥原理+拓展

    ### 容斥原理及其扩展应用 #### 一、容斥原理概述 容斥原理是一种用于计算有限个集合的并集的元素数量的重要方法。它的基本形式可以表示为: \[ |A_1 \cup A_2 \cup \ldots \cup A_n| = \sum_{i=1}^n |A_i| - \...

    poj1088和1091

    "1088滑雪"有助于理解图论和搜索算法,而"1091跳蚤"则涉及到了基础的数论知识。虽然代码可能不那么简洁,但通过解题,初学者可以提升算法设计和逻辑思维能力,这对于成长为一名优秀的程序员至关重要。在实际编程过程...

    容斥原理与莫比乌斯函数.md

    容斥原理与莫比乌斯函数.md

    POJ算法题目分类

    * 数论:数论是指解决问题的数论算法,如 poj2635、poj3292、poj1845、poj2115。 * 计算方法:计算方法是指解决问题的计算方法算法,如 poj3273、poj3258、poj1905、poj3122。 七、计算几何学 计算几何学是指...

    poj题目分类

    * 较为复杂的动态规划:例如 poj1191、poj1054、poj3280、poj2029、poj2948、poj1925、poj3034。 数学 1. 组合数学: * 加法原理和乘法原理。 * 排列组合。 * 递推关系:例如 poj3252、poj1850、poj1019、poj...

    poj训练计划.doc

    - 数论:如`poj2635, poj3292`。 #### 第二阶段中级训练计划 #### 第3周至第4周(共85题) - **进阶算法** - C++标准模版库的应用:如`poj3096, poj3007`。 - 复杂的模拟题:如`poj3393, poj1472`。 - **图...

    poj题目代码

    2. poj_1013.c - "Divisors":此题主要考察了数论和数组处理,要求找出一个数的所有因子,对理解因数分解和遍历数组技巧有帮助。 3. poj_1833.c - "Tic Tac Toe":这是关于井字游戏的实现,涉及到博弈论和回溯算法...

    诸多素数问题与容斥原理.pdf

    标题“诸多素数问题与容斥原理.pdf”和描述中的“李扩继 诸多素数问题与容斥原理.pdf”揭示了文档内容的重点,即对素数问题的研究以及容斥原理的应用。文档内容围绕素数筛法、欧拉函数及其推广、容斥原理等数学概念...

    POJ1426-Find The Multiple【BFS+同余模】

    【标题】"POJ1426-Find The Multiple【BFS+同余模】"是一道来源于北京大学在线编程平台POJ的算法题目,主要涉及到了广度优先搜索(BFS)与同余模运算的知识点。这道题目要求解决的是寻找一个整数的倍数问题,可能...

    初等数论 陈景润的数论

    初等数论是数学中的一个基础分支,主要研究整数的性质和整数之间关系的数学理论。陈景润,中国著名数学家,对数论做出了杰出贡献,尤其以陈氏定理而闻名。在这本书中,我们可以学习到数论的基本知识,并通过陈景润的...

    ACM数学+数论大全

    在ACM(国际大学生程序设计竞赛)中,数学和数论是解决问题的关键工具。下面将对标题和描述中提到的一些重要知识点进行详细说明。 1. **BASIC 3IO挂**:在ACM编程竞赛中,输入/输出(I/O)优化是提高效率的重要环节...

    数论系列之二 初等数论 潘承洞

    潘承洞院士所著的《数论系列之二 初等数论》是一本介绍初等数论基础知识的教材,尤其适合数学系、计算机系、中高等教育院校及教师进修学校的师生,同时对数学工作者、中学数学教师及高中生也具有很高的参考价值。...

    数学概貌丛书++数论概貌(陈景润).pdf

    数学概貌丛书++数论概貌(陈景润).pdf

    算法基础数论

    3. **@cfannet.com@初等数论+I(陈景润).pdf**:陈景润是中国著名的数论学家,他的著作很可能深入浅出地介绍了初等数论的各个方面,可能包含陈氏定理(哥德巴赫猜想的一部分证明)或其他著名的数论猜想。...

    容斥原理解N以下的素数个数

    容斥原理,也被称为Inclusion-Exclusion Principle,在数学中是一种强大的计数工具,尤其在组合数学中用于计算集合元素的总数。这个原理的核心思想是当我们想要计算一个总集合的元素数量时,需要考虑所有子集的贡献...

Global site tag (gtag.js) - Google Analytics