C++博客-王之昊在学数学

C++博客-王之昊在学数学http://www.cppblog.com/logics-space/数论,组合数学,具体数学,离散数学zh-cnTue, 14 Apr 2026 23:07:14 GMTTue, 14 Apr 2026 23:07:14 GMT60合并同余方程组(模不互素)http://www.cppblog.com/logics-space/archive/2010/07/28/121441.htmlwangzhihaowangzhihaoWed, 28 Jul 2010 03:09:00 GMThttp://www.cppblog.com/logics-space/archive/2010/07/28/121441.htmlhttp://www.cppblog.com/logics-space/comments/121441.htmlhttp://www.cppblog.com/logics-space/archive/2010/07/28/121441.html#Feedback0http://www.cppblog.com/logics-space/comments/commentRss/121441.htmlhttp://www.cppblog.com/logics-space/services/trackbacks/121441.html

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 具有唯一解

wangzhihao 2010-07-28 11:09 发表评论

]]>待续http://www.cppblog.com/logics-space/archive/2010/07/19/120836.htmlwangzhihaowangzhihaoMon, 19 Jul 2010 14:02:00 GMThttp://www.cppblog.com/logics-space/archive/2010/07/19/120836.htmlhttp://www.cppblog.com/logics-space/comments/120836.htmlhttp://www.cppblog.com/logics-space/archive/2010/07/19/120836.html#Feedback0http://www.cppblog.com/logics-space/comments/commentRss/120836.htmlhttp://www.cppblog.com/logics-space/services/trackbacks/120836.html阅读全文

wangzhihao 2010-07-19 22:02 发表评论

]]>一个多项式的差分的等价形式---棋盘上放车的种数http://www.cppblog.com/logics-space/archive/2010/07/18/120732.htmlwangzhihaowangzhihaoSun, 18 Jul 2010 13:32:00 GMThttp://www.cppblog.com/logics-space/archive/2010/07/18/120732.htmlhttp://www.cppblog.com/logics-space/comments/120732.htmlhttp://www.cppblog.com/logics-space/archive/2010/07/18/120732.html#Feedback0http://www.cppblog.com/logics-space/comments/commentRss/120732.htmlhttp://www.cppblog.com/logics-space/services/trackbacks/120732.html阅读全文

wangzhihao 2010-07-18 21:32 发表评论

]]>关于划分的问题http://www.cppblog.com/logics-space/archive/2010/07/18/120701.htmlwangzhihaowangzhihaoSun, 18 Jul 2010 08:21:00 GMThttp://www.cppblog.com/logics-space/archive/2010/07/18/120701.htmlhttp://www.cppblog.com/logics-space/comments/120701.htmlhttp://www.cppblog.com/logics-space/archive/2010/07/18/120701.html#Feedback0http://www.cppblog.com/logics-space/comments/commentRss/120701.htmlhttp://www.cppblog.com/logics-space/services/trackbacks/120701.html 感觉以前很少接触到这种划分的问题，但是它又好像很经典的样子阅读全文

wangzhihao 2010-07-18 16:21 发表评论

]]>acm mathhttp://www.cppblog.com/logics-space/archive/2010/06/23/118592.htmlwangzhihaowangzhihaoWed, 23 Jun 2010 15:19:00 GMThttp://www.cppblog.com/logics-space/archive/2010/06/23/118592.htmlhttp://www.cppblog.com/logics-space/comments/118592.htmlhttp://www.cppblog.com/logics-space/archive/2010/06/23/118592.html#Feedback0http://www.cppblog.com/logics-space/comments/commentRss/118592.htmlhttp://www.cppblog.com/logics-space/services/trackbacks/118592.html

题号	摘要	提交次数 / 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= 2P+2(p/2 + 1/2 = 1) 和 S = 2P + 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	数字游戏	分各位十位百位。。。统计，也可以通过二分做，注意不要溢出这题不顺

wangzhihao 2010-06-23 23:19 发表评论

]]>随便写写http://www.cppblog.com/logics-space/archive/2009/09/26/97309.htmlwangzhihaowangzhihaoSat, 26 Sep 2009 12:29:00 GMThttp://www.cppblog.com/logics-space/archive/2009/09/26/97309.htmlhttp://www.cppblog.com/logics-space/comments/97309.htmlhttp://www.cppblog.com/logics-space/archive/2009/09/26/97309.html#Feedback0http://www.cppblog.com/logics-space/comments/commentRss/97309.htmlhttp://www.cppblog.com/logics-space/services/trackbacks/97309.html剩下的就是提高实力了，首先是想法，其次是代码。看大量的书，看大量的论文。做大量的题
要了解自己的队友，要熟悉现在那些人是牛人，多关注牛人，见贤思齐

wangzhihao 2009-09-26 20:29 发表评论

]]>奇迹只会发生在不言放弃的人身上http://www.cppblog.com/logics-space/archive/2009/04/02/78729.htmlwangzhihaowangzhihaoThu, 02 Apr 2009 11:31:00 GMThttp://www.cppblog.com/logics-space/archive/2009/04/02/78729.htmlhttp://www.cppblog.com/logics-space/comments/78729.htmlhttp://www.cppblog.com/logics-space/archive/2009/04/02/78729.html#Feedback1http://www.cppblog.com/logics-space/comments/commentRss/78729.htmlhttp://www.cppblog.com/logics-space/services/trackbacks/78729.html阅读全文

wangzhihao 2009-04-02 19:31 发表评论

]]>Why XAML Needed?http://www.cppblog.com/logics-space/archive/2009/03/30/78370.htmlwangzhihaowangzhihaoMon, 30 Mar 2009 07:14:00 GMThttp://www.cppblog.com/logics-space/archive/2009/03/30/78370.htmlhttp://www.cppblog.com/logics-space/comments/78370.htmlhttp://www.cppblog.com/logics-space/archive/2009/03/30/78370.html#Feedback0http://www.cppblog.com/logics-space/comments/commentRss/78370.htmlhttp://www.cppblog.com/logics-space/services/trackbacks/78370.htmlWhy 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.

wangzhihao 2009-03-30 15:14 发表评论

]]>刷表http://www.cppblog.com/logics-space/archive/2009/03/25/77829.htmlwangzhihaowangzhihaoWed, 25 Mar 2009 06:35:00 GMThttp://www.cppblog.com/logics-space/archive/2009/03/25/77829.htmlhttp://www.cppblog.com/logics-space/comments/77829.htmlhttp://www.cppblog.com/logics-space/archive/2009/03/25/77829.html#Feedback0http://www.cppblog.com/logics-space/comments/commentRss/77829.htmlhttp://www.cppblog.com/logics-space/services/trackbacks/77829.html
Cubic-free numbers II

要求[ L，R )上的不是Cubic数的个数，发现求区间上有多少Cubic数更清晰，求这种区间问题有一种比较经典的处理技巧，求出[1，L)和[1,R)
[L , R) = [1, R) - [1, L);

我们可以用容斥来求区间[1，k）上有多少Cubic数，这里刷表表示容斥就很方便了
唯一注意一点，就是先把含有i*i的数标记成无效，因为我们的容斥不会去判一个集合自己和自己的关系，我们都是比较一个集合和其他集合的关系

Coprimes

这也是一道容斥题，刷表

wangzhihao 2009-03-25 14:35 发表评论

]]>eoj 2474 Star Warshttp://www.cppblog.com/logics-space/archive/2009/03/08/75906.htmlwangzhihaowangzhihaoSun, 08 Mar 2009 08:00:00 GMThttp://www.cppblog.com/logics-space/archive/2009/03/08/75906.htmlhttp://www.cppblog.com/logics-space/comments/75906.htmlhttp://www.cppblog.com/logics-space/archive/2009/03/08/75906.html#Feedback0http://www.cppblog.com/logics-space/comments/commentRss/75906.htmlhttp://www.cppblog.com/logics-space/services/trackbacks/75906.html阅读全文

wangzhihao 2009-03-08 16:00 发表评论

]]>