N(i)=N(t()L=)
h
30
N1nL|n(L)*(xL)^(n/L)
h
31
2888
一条项链，n个珠子，m种颜色，给定k对颜色不能相邻，循环同构，求方 案数？
h
32
h
3
The iterative method
h
4
Recursive method
h
5
Miller Rabbin
• BASIS: That is ,
a^p mod p = a a^(p-1) mod p = 1
TOOLS: power_product
h
6
Cycle detection
Rho
How to calculate :
数论、组合数学、具体数学
李寅
h
1
Euclidean algorithm
• Gcd( a , b ) = gcd( b*(a/b)+(a%b) , b)
•
= gcd( b , a%b )
•
=…
h
2
Extended Euclidean algorithm
The iterative method The recursive method
λ divides ν, xν + μ = xμ, the start of the first
repetition.
• Finally, from xμ it is trivial to find the length of the shortest repeating cycle, xμ + λ = xμ.
You task is to calculate the number of terms in the Farey sequence Fn.
h
22
加减法原理
• 在空间中给出了n个点。这些点任三点不共 线，并且每两个点之间都有一条线相连， 每一条线不是红的就是黑的。在这些点和 线组成的三角形中，如果一个三角形的三 条边的颜色都相同，那么我们就称这个三 角形为单色三角形。现给出所有涂红色的 线，试求出单色三角形的数目。
h
16
Euler Function
h
17
• （1）
• （2）
• （3） （ p ^ n ) (p 1 )* p ^ (n 1 )
• （4） (m ,m ') (m )* (m ')
• （5） ( m ,k ) 1 ,k ^( m ) 1 ( m o d m )
h
18
pku2480
n
f (n) gcd(i,N) i1
• Solution:
f(n) d*(n/d) d|n
d
T r y t o p r o v e ： f( m * m ') f( m ) * f( m ')
h
19
h
20
Euler递推式
• 若(N%a==0 && (N/a)%a==0) 则有:
(n)(n/a)*a
• 若(N%a==0 && (N/a)%a!=0) 则有:
observation that (as in the birthday
paradox) two numbers x and y are congruent modulo p with probability
0.5 after
numbers have been
randomly chosen. If p is a factor of
• Thus, we need only check for repeated values of this special form to find a period ν of a repetition that is a multiple of λ. Once ν is found, we may retrace the sequence from its start to find the first repetition of length ν; since
h
23
• （1）C(n,3) • （2） 1 n ri*(n1ri)
2 i1
h
24
Generating function
h
25
3045
h
26
Group Theory
1 35 26 34 45 21 6 = （ 136） （ 25） （ 4）
h
27
Burnside lemma
h
28
• Rotate i • Number of cycles : gcd(n,i) • Length of cycles: n/gcd(n,i)
Bi - Calculate
h
29
Think it in another way
Li = n/gcd(n,i） L: gcd(n,i) = n/L = a
gcd(aL,i)=a Let i=at, because n>i, aL>at , so L>t
gcd(aL,at)=a gcd(L,t)=1
h
14
• POJ 1811
Practice
h
15
modular_linear_equation
• ax mod n = b • ax = ny + b • ax – ny =b • d = gcd(a, n) • If( b % d !=0 ) :: no solution • else solve ax0 – ny0 = d • X = (x0 * b/d + n) % n
HASH?
h
7
Floyd's cycle-finding algorithm
h
8
• The key insight in the algorithm is that, whenever
i > 0 is a multiple of λ that is greater than μ, xi = x2i (and conversely).
h
9
h
10
Brent's algorithm
• X1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14
h
11
h
12
Pollard Rho – factorize bigint
• The rho algorithm is based on Floyd's cycle-finding algorithm and on the
n, the integer we are aiming to
factor, then
•
since p divides both h
and n. 13
Note that this algorithm will return failure for all prime n, but it can also fail for composite n. In that case, use a different f(x) and try again
(n ) (n/a )*(a 1 )
h
21
• The Farey Sequence Fn for any integer n with n >= 2 is the set of irreducible rational numbers a/b with 0 < a < b <= n and gcd(a,b) = 1 arranged in increasing order. The first few are F2 = {1/2} F3 = {1/3, 1/2, 2/3} F4 = {1/4, 1/3, 1/2, 2/3, 3/4} F5 = {1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5}