2010年7月28日
對(duì)于方程組
- x = a (mod p)
- x = b (mod q)
其中p, q互素。
可以采用中國(guó)剩余定理，
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, 則無(wú)解, 否則
x = q * Eq * a + p * Ep * b ( mod pqd ) , 其中 Eq * q + Ep * p = 1;
可以驗(yàn)算這個(gè)構(gòu)造解是適合上面兩個(gè)方程的。
比如驗(yàn)算第一個(gè)方程：
首先變形得到 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 閱讀(1299) |
評(píng)論 (0) |
編輯 收藏
2010年6月23日
ZOJ
| 題號(hào) |
摘要
|
提交次數(shù) / coding耗時(shí) |
| 2313 |
模板的弊端,具體優(yōu)化
|
13 / ---
|
| 2317 |
走道鋪磚
|
3 / 60"
|
| 2318 |
環(huán)顧法判點(diǎn)在多邊形內(nèi)，搜索樹(shù)，所有回路
|
--- / --- |
PKU
| 題號(hào) |
分類 |
注釋 |
鏈接 |
| 1012 |
遞歸 recursion
|
joseph問(wèn)題，joseph是經(jīng)典的遞歸問(wèn)題 |
|
| 1186 |
雙向枚舉
|
現(xiàn)枚舉前一半，再二分查找后一半是否有對(duì)應(yīng)的值
|
|
| 1285 |
組合 & 計(jì)數(shù)
|
有限制的可重復(fù)排列
dp （pku 的 G++不識(shí) unsigned long long 尷尬）
|
|
| 1286 |
burnside
|
2154的簡(jiǎn)化版 |
|
| 1316 |
質(zhì)因數(shù)分解 Prime- factor
|
有點(diǎn)進(jìn)制轉(zhuǎn)換的感覺(jué) |
:D |
| 1351 |
組合 & 計(jì)數(shù)
|
有相鄰問(wèn)題可重復(fù)的排列
dfs |
|
1430
|
stirling數(shù)
|
很考察觀察能力
|
|
| 1715 |
組合 & 計(jì)數(shù)
|
詢問(wèn)第n位上是哪個(gè)數(shù)，比較常見(jiàn)的一類題 |
|
| 1718 |
joseph
|
計(jì)算倒數(shù)第二個(gè)被殺的人是誰(shuí) |
|
| 1737 |
遞歸 recursion
|
其實(shí)不是很復(fù)雜
|
|
| 1809 |
奇偶性
|
奇偶性 |
|
| 1811 |
miller-rabin + pollard rho
|
很適合初學(xué)這兩種算法 |
|
| 1831 |
枚舉 構(gòu)造
|
枚舉幾項(xiàng)小的，再用S= 2*P+2(p/2 + 1/2 = 1) 和 S = 2*P + 9(p/2 + １＋1/3 + 1/6 = 1)構(gòu)造
|
|
| 1845 |
積性函數(shù) |
積性函數(shù) |
|
| 2034 |
反素?cái)?shù) antiprime
|
dfs |
:D |
| 2142 |
解不定方程 |
解不定整數(shù)方程ax + by = c 其中a，b，c ，x，y為整數(shù)
|
|
| 2154 |
burnside 歐拉數(shù) 觀察
|
想法不算繞彎，只要知道這些知識(shí)點(diǎn)完全能解出來(lái) |
:D |
| 2282 |
數(shù)字游戲
|
統(tǒng)計(jì)[a，b]中0,1,2...9的個(gè)數(shù)
|
|
| 2429 |
質(zhì)因數(shù)分解 pollard rho
|
pollard rho
|
|
| 2689 |
素?cái)?shù) prime
|
刷表
|
:) |
| 2739 |
素?cái)?shù) prime
|
暴力 |
|
| 2769 |
同余
|
刷表 |
|
| 2891 |
合并同余方程
|
合并同余方程 |
|
| 2917 |
質(zhì)因數(shù) |
分解質(zhì)因數(shù) |
|
| 2992 |
約數(shù) divisor
|
分解連續(xù)的數(shù)的質(zhì)因數(shù) 水題
|
|
| 3126 |
素?cái)?shù) prime |
其實(shí)重點(diǎn)不是prime。。。 bfs關(guān)鍵 |
|
| 3128 |
循環(huán)節(jié)
|
找規(guī)律 |
|
| 3132 |
素?cái)?shù) prime
|
其實(shí)重點(diǎn)不是prime。。。 dp關(guān)鍵 -_-!
|
|
| 3252 |
數(shù)字游戲
|
算[a,b]里有多少數(shù)的二進(jìn)制0比1多 |
|
| 3324 |
大數(shù) +針對(duì)該題目的一些優(yōu)化
|
mod （2^p-1）可以優(yōu)化 |
|
| 3508 |
大數(shù)加法
|
大數(shù)加法 |
|
| 3518 |
素?cái)?shù) prime
|
二分 |
|
| 3641 |
素?cái)?shù) prime
|
miller-rabin 注意 a^p%p=a 不等價(jià)與 a^(p-1)%p=1
|
|
| 3725 |
數(shù)字游戲
|
分各位十位百位。。。統(tǒng)計(jì)， 也可以通過(guò)二分做，注意不要溢出這題不順
|
|
posted @
2010-06-23 23:19 wangzhihao 閱讀(459) |
評(píng)論 (0) |
編輯 收藏
2009年9月26日
要有激情
剩下的就是提高實(shí)力了，首先是想法，其次是代碼。看大量的書(shū)，看大量的論文。做大量的題
要了解自己的隊(duì)友，要熟悉現(xiàn)在那些人是牛人，多關(guān)注牛人，見(jiàn)賢思齊
posted @
2009-09-26 20:29 wangzhihao 閱讀(191) |
評(píng)論 (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 閱讀(245) |
評(píng)論 (0) |
編輯 收藏
2009年3月25日
刷表就是一種預(yù)處理
Cubic-free numbers II
要求[ L，R )上的不是Cubic數(shù)的個(gè)數(shù)，發(fā)現(xiàn)求區(qū)間上有多少Cubic數(shù)更清晰，求這種區(qū)間問(wèn)題有一種比較經(jīng)典的處理技巧，求出[1，L)和[1,R)
[L , R) = [1, R) - [1, L);
我們可以用容斥來(lái)求區(qū)間[1，k）上有多少Cubic數(shù)，這里刷表表示容斥就很方便了
唯一注意一點(diǎn)，就是先把含有i*i的數(shù)標(biāo)記成無(wú)效，因?yàn)槲覀兊娜莩獠粫?huì)去判一個(gè)集合自己和自己的關(guān)系，我們都是比較一個(gè)集合和其他集合的關(guān)系
Coprimes
這也是一道容斥題，刷表
posted @
2009-03-25 14:35 wangzhihao 閱讀(203) |
評(píng)論 (0) |
編輯 收藏