随笔-21  评论-10  文章-21  trackbacks-0
 
对于方程组
  • 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 阅读(1171) | 评论 (0)编辑 收藏
     摘要: 待续  阅读全文
posted @ 2010-07-19 22:02 wangzhihao 阅读(207) | 评论 (0)编辑 收藏
     摘要: 一个多项式的差分的等价形式---棋盘上放车的种数  阅读全文
posted @ 2010-07-18 21:32 wangzhihao 阅读(386) | 评论 (0)编辑 收藏
     摘要:
感觉以前很少接触到这种划分的问题,但是它又好像很经典的样子  阅读全文
posted @ 2010-07-18 16:21 wangzhihao 阅读(210) | 评论 (0)编辑 收藏
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+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 阅读(412) | 评论 (0)编辑 收藏
要有激情
剩下的就是提高实力了,首先是想法,其次是代码。看大量的书,看大量的论文。做大量的题
要了解自己的队友,要熟悉现在那些人是牛人,多关注牛人,见贤思齐


posted @ 2009-09-26 20:29 wangzhihao 阅读(154) | 评论 (0)编辑 收藏
     摘要: 奇迹只会发生在不言放弃的人身上  阅读全文
posted @ 2009-04-02 19:31 wangzhihao 阅读(328) | 评论 (1)编辑 收藏
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 阅读(207) | 评论 (0)编辑 收藏
刷表就是一种预处理

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 阅读(166) | 评论 (0)编辑 收藏
     摘要:   阅读全文
posted @ 2009-03-08 16:00 wangzhihao 阅读(149) | 评论 (0)编辑 收藏
仅列出标题
共3页: 1 2 3