- 博客(16)
- 资源 (4)
- 收藏
- 关注
RSS订阅原创 10604 - Chemical Reaction解题报告
//这道题就只有我用的状态DP么？//DP时取当前的试剂组合，得出它们组成各种试剂的最小热量，以组合为状态就好#include #include #include using namespace std;const int N = 7, inf = 0x7f7f7f7f;struct Edge{ int a, b, emit, nxt;}edge[N * N];in
2013-05-31 20:22:24
950
原创 数论概论笔记 第14章 梅森素数
命题14.1 如果对整数 a ≥ 2 与n ≥ 2， 如 a^n - 1 是素数， 则 a 必等于2且 n 一定是素数。定义：设p为素数，形如 2^p - 1的素数称为梅森素数。
2013-04-06 16:38:02
567
原创 数论概论笔记 第13章 素数计数
定理13.1 素数定理：当x很大时，小于x的素数个数近似等于 x / ln(x)， 即lim(x → ∞) π(x) / ( x / ln(x) ) = 1。猜想13.2 哥德巴赫猜想：每个大于4的偶数可以表示为两个素数之和。猜想13.3 孪生素数猜想：存在无数个素数 p 使得p + 2 也是素数。孪生素数计数：lim(x → ∞) T(x) / (x
2013-04-06 16:33:28
637
原创 数论概论笔记 第12章 素数
定理12.1 无穷多素数定理：存在无穷多个素数。欧几里得证明：假定已列出有限素数表， 由 p[1], p[2], p[3],……p[r]组成则有数 A = p[1] * p[2] * p[3] *…… * p[r] + 1，如A为素数，则其必大于素数表中的任意素数，故不在素数表中；如A为合数，则A定能被某素数q整除，有q | (p[1] * p[2] * p[3] *……
2013-04-06 16:21:18
1161
原创 数论概论笔记 第11章 欧拉Φ函数与中国剩余定理
定理11.1 Φ函数公式：(a) 如果p是素数且k ≥ 1， 则 Φ(p ^ k) = p ^ k - p ^ (k - 1)；(b) 如果 gcd(m, n) = 1, 则 Φ(mn) = Φ(m) Φ(n)定理11.1证明：定理11.1 (a) 证明：当m = p ^ k，p 是素数， [1, m) 内的a 被 p 整除时，a 不与 p ^ k 互素，即Φ(p ^
2013-03-25 21:36:42
751
原创 数论概论笔记 第10章 同余式、幂与欧拉函数
终于到第10章了，竟然能坚持看下来……欧拉函数定义：对于正整数m，在0 与m 之间与 m 互素的整数个数为欧拉函数，即 Φ(m) = # {a : 1 ≤ a ≤ m, gcd(a, m) = 1}。注：对正整数 m > 2，有 Ф(m) 为偶数。证明略。p是素数是吗，每个整数 1 ≤ a ≤ (p - 1) 都与p互素，故有 p 为素数时Φ(p) = p - 1；定
2013-03-20 16:30:18
647
原创 数论概论笔记 第9章 同余式、幂与费马小定理
定理9.1 费马小定理：设 p 是素数，a 是任意整数且 a !≡ 0 (mod p)（不同余符号打不出来）则a^(p - 1) ≡ 1 (mod p)断言9.2：设 p 是素数，a 是任意整数且 a !≡ 0 (mod p)，则数a, 2a, 3a, ……(p - 1)a (mod p)
2013-03-18 15:26:05
715
原创 数论概论笔记 第8章 同余式
同余：如有 m 整除 a - b ，则称 a 与 b 同余，并记之为：a ≡ b (mod m)。如 a 除以 m 余 r，则 a 与 r 模 m 同余，0 ≤ r 同余的四则运算：如 a1 ≡ b1 (mod m), a2 ≡ b2 (mod m)，则：a1 ± b1 ≡ (b1 ± b2) (mod m)，a1*a2 ≡ b1 * b2 (mod m)；如 ac ≡ b
2013-03-17 18:44:42
843
原创 数论概论笔记 第7章 因数分解与算数基本定理
素数定义：如 p ≥ 2 且p只能被1或自身整除，则p为素数。断言7.1 令 p 是素数，如 p 整除乘积 ab，则 p 整除 a 或 p 整除 b。证明如下：如 p 整除 a，则命题成立；如 p 不整除 a，则有 gcd(a, p) = 1；根据第6章的定理，可得方程ax + py = gcd(a, p) = 1；abx + pby = b；已知 p 可整除 ab
2013-03-16 13:37:23
843
原创 数论概论笔记 第6章 线性方程与最大公因数
定理：形如 ax + by 的二元整数式的最小正整数等于 gcd(a, b)，证明略；由欧几里得算法，有：a = q1 * b + r1r1 = a - q1 * bb = q2 * r1 + r2r2 = b - q2 * r1 = -q2 * a + (1 + q1 * q2) * br1 = q3 * r2 + r3r3 = r1
2013-03-15 20:19:26
690
原创 uva 11121 - Base -2
求一个数的（-2）进制形式。虽说是-2，本质不还是位运算，穿个马甲我就不认识你了？#include using namespace std;const int N = 105;char str[N];int main(){ #ifdef LOCAL freopen("in", "r", stdin); #endif int T, cur;
2013-03-15 12:37:22
706
原创 uva 10673 - Play with Floor and Ceil
这道题拿到手很快就做完了。AC之后看了一下别人的解题报告，都是用的扩展gcd。不过这题没必要这样吧。我的做法如下：设 y = x % k；则原式可表示为 x = p * (x / k - y / k) + q * (x / k + (k - y) / k)；化简上式可得：p + q = k， p * y = q * (k - y)，即(p + y) * y = k * y
2013-03-15 08:45:35
575
原创 数论概论笔记 第5章 整除性与最大公因数
素数、公因数和互质的定义不必再说。欧几里得算法（辗转相除法）：要计算两个整数a和b的最大公因数，先令 r[-1] = a 且 r[0] = b，然后计算相继的商和余数r[i - 1] = q[i + 1] ×r[i] + r[i + 1], (i = 0, 1, 2 ……)，知道某余数r[n + 1]为0，最后的非零余数r[n]就是a和b的最大公因数。现证明该算法的正确性，证
2013-03-15 02:12:15
620
原创 数论概论笔记 第4章 高次幂之和与费马大定理
费马大定理：对方程 a^n + b^n = c^n， n∈N，当n ≥ 2 时，方程没有正整数解。证明……我是不会啦。
2013-03-15 01:46:06
476
原创 数论概论笔记 第3章 勾股数组与单位圆
已知单位圆方程为 x^2 + y^2 = 1。现欲求圆上所有坐标为有理数的点。现有一条经过点(-1, 0)的直线，其方程为 y = m × (x + 1)，m∈Q；可得单位圆和直线的交点坐标为(-1, 0) 和 ((1 - m ^ 2) / (1 + m^2), 2m / (1 + m^2))。因为m∈Q，所以所得的第二点的坐标为有理数。另一方面，如得到一个有理数借(
2013-03-15 01:40:19
612
原创 数论概论笔记 第2章 勾股数组
毕达哥拉斯定理（勾股定理）：a^2 + b^2 = c^2; 有a,b,c∈N本原勾股数组（PPT）是一个三元组（a,b,c），其中a, b, c没有公因数，且满足a^2 + b^2 = c^2可证明a,b的奇偶性不同且c为奇数。证明如下：如a, b为偶数，则c必为偶数，a, b, c不互质，不构成勾股数组；如a, b为奇数，则c必为偶数。设a = 2 x + 1, b =
2013-03-15 00:21:27
719
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人