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;
}
分享到:
相关推荐
容斥原理是指,在数论中,容斥原理是一种常用的计算技术,用于计算满足某些条件的整数个数。 容斥原理的基本思想是,先计算满足某些条件的整数个数,然后再减去满足其他条件的整数个数,从而得到满足所有条件的整数...
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
POJ1091跳蚤,则引导他们深入数论的海洋,学会在纷繁的数学关系中寻找规律。尽管代码初稿可能略显粗糙,但正是通过解决这些问题,初学者的算法设计能力得以增强,逻辑思维也变得更加敏锐。 然而,对于任何一位希望...
数论,作为数学的一个分支,主要研究整数的性质,特别是它们之间的关系和结构。它在密码学、编码理论、计算机科学以及纯数学的多个领域都有广泛应用。本资源包含两个文件,分别是“数论.pdf”和“数论讲义+上册.rar...
+ 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| - \...
容斥原理与莫比乌斯函数.md
* 数论:数论是指解决问题的数论算法,如 poj2635、poj3292、poj1845、poj2115。 * 计算方法:计算方法是指解决问题的计算方法算法,如 poj3273、poj3258、poj1905、poj3122。 七、计算几何学 计算几何学是指...
* 较为复杂的动态规划:例如 poj1191、poj1054、poj3280、poj2029、poj2948、poj1925、poj3034。 数学 1. 组合数学: * 加法原理和乘法原理。 * 排列组合。 * 递推关系:例如 poj3252、poj1850、poj1019、poj...
- 数论:如`poj2635, poj3292`。 #### 第二阶段中级训练计划 #### 第3周至第4周(共85题) - **进阶算法** - C++标准模版库的应用:如`poj3096, poj3007`。 - 复杂的模拟题:如`poj3393, poj1472`。 - **图...
2. poj_1013.c - "Divisors":此题主要考察了数论和数组处理,要求找出一个数的所有因子,对理解因数分解和遍历数组技巧有帮助。 3. poj_1833.c - "Tic Tac Toe":这是关于井字游戏的实现,涉及到博弈论和回溯算法...
标题“诸多素数问题与容斥原理.pdf”和描述中的“李扩继 诸多素数问题与容斥原理.pdf”揭示了文档内容的重点,即对素数问题的研究以及容斥原理的应用。文档内容围绕素数筛法、欧拉函数及其推广、容斥原理等数学概念...
1. **数论**:包括素数判定、欧几里得算法、扩展欧几里得算法等(poj2488, poj3083, poj3009, poj1321, poj2251)。 2. **组合数学**:如排列组合计算(poj3278, poj1426, poj3126, poj3087.poj3414)。 3. **矩阵...
【标题】"POJ1426-Find The Multiple【BFS+同余模】"是一道来源于北京大学在线编程平台POJ的算法题目,主要涉及到了广度优先搜索(BFS)与同余模运算的知识点。这道题目要求解决的是寻找一个整数的倍数问题,可能...
初等数论是数学中的一个基础分支,主要研究整数的性质和整数之间关系的数学理论。陈景润,中国著名数学家,对数论做出了杰出贡献,尤其以陈氏定理而闻名。在这本书中,我们可以学习到数论的基本知识,并通过陈景润的...
潘承洞院士所著的《数论系列之二 初等数论》是一本介绍初等数论基础知识的教材,尤其适合数学系、计算机系、中高等教育院校及教师进修学校的师生,同时对数学工作者、中学数学教师及高中生也具有很高的参考价值。...
在ACM(国际大学生程序设计竞赛)中,数学和数论是解决问题的关键工具。下面将对标题和描述中提到的一些重要知识点进行详细说明。 1. **BASIC 3IO挂**:在ACM编程竞赛中,输入/输出(I/O)优化是提高效率的重要环节...
4. POJ——2676 整数的个数:这可能需要对数论有基础了解,计算某个区间内的整数个数,可能需要掌握范围内的数学计算。 5. POJ——2679 整数的立方和:可能需要掌握高精度计算,以及求序列和的技巧,例如前n项立方...
数学概貌丛书++数论概貌(陈景润).pdf