2010年7月28日
对于方程组
- x = a (mod p)
- x = b (mod q)
其中p, q互素。
可以采用中国剩余定理，
x = q * Eq * a + p * Ep * b (mod pq ) , 其中 Eq * q + Ep * p = 1;
而模不互素的情况，却有类似的形式：
- x = a (mod pd)
- x = b (mod qd)
其中p, q互素, d > 1。
如果d 不整除 a - b, 则无解, 否则
x = q * Eq * a + p * Ep * b ( mod pqd ) , 其中 Eq * q + Ep * p = 1;
可以验算这个构造解是适合上面两个方程的。
比如验算第一个方程：
首先变形得到 x = (1 - Ep * p ) * a + Ep * p * b (mod pd);
又有：x = a + Ep * p *( b - a ) (mod pd);
又有：d | (b - a) 所以 pd | p*(b - a)
所以 x = a ( mod pd )
也可以证明x 模上 pqd 具有唯一解
posted @
2010-07-28 11:09 wangzhihao 阅读(1244) |
评论 (0) |
编辑 收藏
2010年6月23日
ZOJ
| 题号 |
摘要
|
提交次数 / coding耗时 |
| 2313 |
模板的弊端,具体优化
|
13 / ---
|
| 2317 |
走道铺砖
|
3 / 60"
|
| 2318 |
环顾法判点在多边形内，搜索树，所有回路
|
--- / --- |
PKU
| 题号 |
分类 |
注释 |
链接 |
| 1012 |
递归 recursion
|
joseph问题，joseph是经典的递归问题 |
|
| 1186 |
双向枚举
|
现枚举前一半，再二分查找后一半是否有对应的值
|
|
| 1285 |
组合 & 计数
|
有限制的可重复排列
dp （pku 的 G++不识 unsigned long long 尴尬）
|
|
| 1286 |
burnside
|
2154的简化版 |
|
| 1316 |
质因数分解 Prime- factor
|
有点进制转换的感觉 |
:D |
| 1351 |
组合 & 计数
|
有相邻问题可重复的排列
dfs |
|
1430
|
stirling数
|
很考察观察能力
|
|
| 1715 |
组合 & 计数
|
询问第n位上是哪个数，比较常见的一类题 |
|
| 1718 |
joseph
|
计算倒数第二个被杀的人是谁 |
|
| 1737 |
递归 recursion
|
其实不是很复杂
|
|
| 1809 |
奇偶性
|
奇偶性 |
|
| 1811 |
miller-rabin + pollard rho
|
很适合初学这两种算法 |
|
| 1831 |
枚举 构造
|
枚举几项小的，再用S= 2*P+2(p/2 + 1/2 = 1) 和 S = 2*P + 9(p/2 + １＋1/3 + 1/6 = 1)构造
|
|
| 1845 |
积性函数 |
积性函数 |
|
| 2034 |
反素数 antiprime
|
dfs |
:D |
| 2142 |
解不定方程 |
解不定整数方程ax + by = c 其中a，b，c ，x，y为整数
|
|
| 2154 |
burnside 欧拉数 观察
|
想法不算绕弯，只要知道这些知识点完全能解出来 |
:D |
| 2282 |
数字游戏
|
统计[a，b]中0,1,2...9的个数
|
|
| 2429 |
质因数分解 pollard rho
|
pollard rho
|
|
| 2689 |
素数 prime
|
刷表
|
:) |
| 2739 |
素数 prime
|
暴力 |
|
| 2769 |
同余
|
刷表 |
|
| 2891 |
合并同余方程
|
合并同余方程 |
|
| 2917 |
质因数 |
分解质因数 |
|
| 2992 |
约数 divisor
|
分解连续的数的质因数 水题
|
|
| 3126 |
素数 prime |
其实重点不是prime。。。 bfs关键 |
|
| 3128 |
循环节
|
找规律 |
|
| 3132 |
素数 prime
|
其实重点不是prime。。。 dp关键 -_-!
|
|
| 3252 |
数字游戏
|
算[a,b]里有多少数的二进制0比1多 |
|
| 3324 |
大数 +针对该题目的一些优化
|
mod （2^p-1）可以优化 |
|
| 3508 |
大数加法
|
大数加法 |
|
| 3518 |
素数 prime
|
二分 |
|
| 3641 |
素数 prime
|
miller-rabin 注意 a^p%p=a 不等价与 a^(p-1)%p=1
|
|
| 3725 |
数字游戏
|
分各位十位百位。。。统计， 也可以通过二分做，注意不要溢出这题不顺
|
|
posted @
2010-06-23 23:19 wangzhihao 阅读(431) |
评论 (0) |
编辑 收藏
2009年9月26日
要有激情
剩下的就是提高实力了，首先是想法，其次是代码。看大量的书，看大量的论文。做大量的题
要了解自己的队友，要熟悉现在那些人是牛人，多关注牛人，见贤思齐
posted @
2009-09-26 20:29 wangzhihao 阅读(164) |
评论 (0) |
编辑 收藏
2009年3月30日
Why XAML Needed?
Since WPF applications can be developed entirely in code, you may ask a
perfectly natural question – why do we need XAML in the first place? The
reason can be traced back to the question of efficiently implementing complex,
graphically rich applications. A long time ago, developers realized that the most
efficient way to develop these kinds of applications was to separate the graphics
portion from the underlying code. In this way, the designers could work on the
graphics, while the developers could work on the code behind the graphics. Both
parts could be designed and refined separately, without any versioning
headaches.
Before WPF, it was impossible to separate the graphics content from the code.
For example, when you work with Windows Forms, you define every form
entirely in C# code or any other language. As you add controls to the UI and
configure them, the program needs to adjust the code in corresponding form
classes. If you want to decorate your forms, buttons, and other controls with
graphics developed by designers, you must extract the graphic content and
export it to a bitmap format. This approach works for simple applications;
however, it is very limited for complex, dynamic applications. Plus, graphics in
bitmap format can lose their quality when they get resized.
The XAML technology introduced in WPF resolves these issues. When you
develop a WPF application in Visual Studio, the window you are creating isn’t
translated into code. Instead, it is serialized into a set of XAML tags. When you
run the application, these tags are used to generate the objects that compose the
UI.
XAML isn’t a must in order to develop WPF applications. You can implement
your WPF applications entirely in code. However, the windows and controls
created in code will be locked into the Visual Studio environment and available
only to programmers; there is no way to separate the graphics portion from the
code.
In orther words, WPF doesn’t require XAML. However, XAML opens up world
of possibilities for collaboration, because many design tools understand the
XAML format.
posted @
2009-03-30 15:14 wangzhihao 阅读(219) |
评论 (0) |
编辑 收藏
2009年3月25日
刷表就是一种预处理
Cubic-free numbers II
要求[ L，R )上的不是Cubic数的个数，发现求区间上有多少Cubic数更清晰，求这种区间问题有一种比较经典的处理技巧，求出[1，L)和[1,R)
[L , R) = [1, R) - [1, L);
我们可以用容斥来求区间[1，k）上有多少Cubic数，这里刷表表示容斥就很方便了
唯一注意一点，就是先把含有i*i的数标记成无效，因为我们的容斥不会去判一个集合自己和自己的关系，我们都是比较一个集合和其他集合的关系
Coprimes
这也是一道容斥题，刷表
posted @
2009-03-25 14:35 wangzhihao 阅读(175) |
评论 (0) |
编辑 收藏