前置容斥原理，最精简的形式应当如此写成：
有 n n n A 1 , … , A n A_1, \dots, A_n A 1 , … , A n S = { A 1 , … , A n } S = \{A_1, \dots, A_n\} S = { A 1 , … , A n }
则有 ∣ ⋃ i = 1 n A i ∣ = ∑ T ∈ 2 S ( − 1 ) ∣ T ∣ − 1 ∣ ⋂ X ∈ T X ∣ \displaystyle\left|\bigcup_{i = 1}^n A_i\right|=\sum_{T\in2^{S}}(-1)^{|T|-1}\left|\bigcap_{X\in T}X\right| i = 1 ⋃ n A i = T ∈ 2 S ∑ ( − 1 ) ∣ T ∣ − 1 X ∈ T ⋂ X
考察欧拉函数通项公式，不妨从容斥的角度来理解：
欲证明 φ ( n ) = n ∏ i = 1 k ( 1 − 1 p i ) \displaystyle\varphi(n) = n\prod_{i=1}^{k}\left(1-\frac{1}{p_i}\right) φ ( n ) = n i = 1 ∏ k ( 1 − p i 1 )
P.f. ：令 A i A_i A i p i p_i p i k k k ⩽ n \leqslant n ⩽ n S = { A 1 , … , A k } S = \{A_1, \dots, A_k\} S = { A 1 , … , A k } ∣ A i ∣ = ⌊ n p i ⌋ \left|A_i\right| = \lfloor\frac{n}{p_i}\rfloor ∣ A i ∣ = ⌊ p i n ⌋ φ ( n ) = n − ∣ ⋃ i = 1 k A i ∣ = n − ∑ T ∈ 2 S ( − 1 ) ∣ T ∣ − 1 ∣ ⋂ X ∈ T X ∣ = n − ∑ T ∈ 2 S ( − 1 ) ∣ T ∣ − 1 n ∏ p = n − ( ∑ i = 1 k n p i ) + ( ∑ i = 1 k ∑ j = i + 1 k n p i p j ) − ⋯ = n ( 1 − ( ∑ i = 1 k 1 p i ) + ( ∑ i = 1 k ∑ j = i + 1 k 1 p i p j ) − ⋯ ) = n ∏ i = 1 k ( 1 − 1 p i ) \displaystyle\varphi(n) = n-\left|\bigcup_{i=1}^k A_i\right|=n-\sum_{T\in2^{S}}(-1)^{|T|-1}\left|\bigcap_{X\in T}X\right|=n-\sum_{T\in2^{S}}(-1)^{|T|-1}\frac{n}{\prod p}=n-\left(\sum_{i=1}^k\frac{n}{p_i}\right)+\left(\sum_{i=1}^k\sum_{j=i+1}^{k}\frac{n}{p_ip_j}\right)-\cdots=n
\left(1-\left(\sum_{i=1}^k\frac{1}{p_i}\right)+\left(\sum_{i=1}^k\sum_{j=i+1}^{k}\frac{1}{p_ip_j}\right)-\cdots\right) = n\prod_{i=1}^k\left(1-\frac{1}{p_i}\right) φ ( n ) = n − i = 1 ⋃ k A i = n − T ∈ 2 S ∑ ( − 1 ) ∣ T ∣ − 1 X ∈ T ⋂ X = n − T ∈ 2 S ∑ ( − 1 ) ∣ T ∣ − 1 ∏ p n = n − ( i = 1 ∑ k p i n ) + ( i = 1 ∑ k j = i + 1 ∑ k p i p j n ) − ⋯ = n ( 1 − ( i = 1 ∑ k p i 1 ) + ( i = 1 ∑ k j = i + 1 ∑ k p i p j 1 ) − ⋯ ) = n i = 1 ∏ k ( 1 − p i 1 )
解释一下推导的最后一步，考虑组合意义，r.h.s. 相当于在多项式凑系数，1 1 1 1 p \frac{1}{p} p 1
从积性的角度：
P.f. ：易证 φ ( p α ) = p α − p α − 1 \varphi(p^\alpha)=p^\alpha-p^{\alpha-1} φ ( p α ) = p α − p α − 1 [ 1 , … p ] , [ p + 1 , … , 2 p ] , … , [ p α − 1 + 1 , p α ] [1,\dots p], [p+1, \dots, 2p], \dots, [p^{\alpha-1}+1, p^\alpha] [ 1 , … p ] , [ p + 1 , … , 2 p ] , … , [ p α − 1 + 1 , p α ] ⊥̸ p α \not\perp p^\alpha ⊥ p α p α − 1 p^{\alpha-1} p α − 1 φ ( n ) = ∏ i = 1 k φ ( p i α i ) = ∏ i = 1 k ( p i α i − p i α i − 1 ) = n ∏ i = 1 k ( 1 − 1 p i ) \displaystyle\varphi(n) = \prod_{i=1}^k\varphi(p_i^{\alpha_{i}}) = \prod_{i=1}^k\left(p_i^{\alpha_{i}}-p_i^{\alpha_i-1}\right)=n\prod_{i=1}^k\left(1-\frac{1}{p_i}\right) φ ( n ) = i = 1 ∏ k φ ( p i α i ) = i = 1 ∏ k ( p i α i − p i α i − 1 ) = n i = 1 ∏ k ( 1 − p i 1 )
结合以上两种证明可以顺便证明欧拉函数的积性。
写出 CRT 所解决的线性同余方程组问题：
求解方程 x ≡ a i ( m o d p i ) x\equiv a_i\pmod{p_i} x ≡ a i ( mod p i )
Sol. ：考虑构造
咕咕咕
类欧几里得。
给定非负整数 n , a , b , c n,a,b,c n , a , b , c f ( n , a , b , c ) = ∑ i = 1 n ⌊ a i + b c ⌋ f(n, a, b, c) = \displaystyle\sum_{i=1}^n\lfloor\frac{ai+b}{c}\rfloor f ( n , a , b , c ) = i = 1 ∑ n ⌊ c ai + b ⌋
Sol. pt 1 ：首先若 a ⩾ c a\geqslant c a ⩾ c b ⩾ c b\geqslant c b ⩾ c a < c a<c a < c b < c b<c b < c a < c a<c a < c b < c b<c b < c m = ⌊ a n + b c ⌋ m=\lfloor\frac{an+b}{c}\rfloor m = ⌊ c an + b ⌋ ∀ x ∈ N , x = ∑ i = 1 + ∞ [ i ⩽ x ] \displaystyle\forall x\in\mathbb{N},x=\sum_{i=1}^{+\infty}[i \leqslant x] ∀ x ∈ N , x = i = 1 ∑ + ∞ [ i ⩽ x ] ∑ i = 1 n ∑ j = 1 m [ j ⩽ ⌊ a i + b c ⌋ ] = ∑ j = 1 m ∑ i = 1 n [ a i ⩾ c j − b ] = n m − ∑ j = 1 m ∑ i = 1 n [ a i ⩽ c j − b − 1 ] = n m − ∑ j = 1 m ∑ i = 1 n [ i ⩽ ⌊ c j − b − 1 a ⌋ ] = n m − f ( m , c , − b − 1 , a ) \displaystyle\sum_{i=1}^n\sum_{j=1}^{m}[j \leqslant \lfloor \frac{ai+b}{c} \rfloor]=\sum_{j=1}^m \sum_{i=1}^n [ai \geqslant cj-b]=nm-\sum_{j=1}^m \sum_{i=1}^n [ai \leqslant cj-b-1]=nm-\sum_{j=1}^m \sum_{i=1}^n [i \leqslant \lfloor\frac{cj-b-1}{a}\rfloor] = nm-f(m, c, -b-1, a) i = 1 ∑ n j = 1 ∑ m [ j ⩽ ⌊ c ai + b ⌋] = j = 1 ∑ m i = 1 ∑ n [ ai ⩾ c j − b ] = nm − j = 1 ∑ m i = 1 ∑ n [ ai ⩽ c j − b − 1 ] = nm − j = 1 ∑ m i = 1 ∑ n [ i ⩽ ⌊ a c j − b − 1 ⌋] = nm − f ( m , c , − b − 1 , a ) − b − 1 -b-1 − b − 1 b b b f f f
Sol. pt 2 ：更改定义 f ( n , a , b , c ) = ∑ i = 0 n ⌊ a i + b c ⌋ f(n, a, b, c) = \displaystyle\sum_{i=\color{red}0}^n\lfloor\frac{ai+b}{c}\rfloor f ( n , a , b , c ) = i = 0 ∑ n ⌊ c ai + b ⌋ g g g h h h f ( n , a , b , c ) = n m − f ( m − 1 , c , c − b − 1 , a ) f(n, a, b, c) = nm-f(m-1, c, c-b-1, a) f ( n , a , b , c ) = nm − f ( m − 1 , c , c − b − 1 , a )
让我们定义 s k ( n ) = ∑ i = 1 n i k \displaystyle s_k(n) = \sum_{i=1}^n i^k s k ( n ) = i = 1 ∑ n i k
大致代码长这样：
int floor_sum(LL n, int a, int b, int c) {
// @returns: \sum_{i=0}^n floor((ai+b)/c)
if (a == 0) {
return mul(safe_mod(n+1), safe_mod(b/c));
}
if (a >= c || b >= c) {
return add(floor_sum(n, a%c, b%c, c), mul(s(n), safe_mod(a/c)), mul(safe_mod(n+1), safe_mod(b/c)));
}
LL m = (a*n+b)/c;
return sub(mul(safe_mod(n), safe_mod(m)), floor_sum(m-1, c, c-b-1, a));
}
给定非负整数 n , a , b , c n, a, b, c n , a , b , c g ( n , a , b , c ) = ∑ i = 0 n ⌊ a i + b c ⌋ 2 g(n, a, b, c) = \sum_{i=0}^n \lfloor\frac{ai+b}{c}\rfloor^2 g ( n , a , b , c ) = ∑ i = 0 n ⌊ c ai + b ⌋ 2 h ( n , a , b , c ) = ∑ i = 0 n i ⌊ a i + b c ⌋ h(n, a, b, c) = \sum_{i=0}^n i\lfloor \frac{ai+b}{c} \rfloor h ( n , a , b , c ) = ∑ i = 0 n i ⌊ c ai + b ⌋
Sol. ：汲取先前的教训，我们将 0 0 0
g g g
c ⩽ max { a , b } c \leqslant \max\{a, b\} c ⩽ max { a , b } g ( n , a , b , c ) = ∑ i = 0 n ( ⌊ ( a m o d c ) i + b m o d c c + i ⌊ a c ⌋ + ⌊ b c ⌋ ⌋ ) 2 = g ( n , a m o d c , b m o d c , c ) + 2 ⌊ a c ⌋ h ( n , a m o d c , b m o d c , c ) + 2 ⌊ b c ⌋ f ( n , a m o d c , b m o d c , c ) + s 2 ( n ) ⌊ a c ⌋ 2 + n ( n + 1 ) ⌊ a c ⌋ ⌊ b c ⌋ + ( n + 1 ) ⌊ b c ⌋ 2 \displaystyle g(n, a, b, c) = \sum_{i=0}^n \left( \lfloor\frac{(a\bmod c)i+b\bmod c}{c}+i \lfloor \frac{a}{c} \rfloor+\lfloor \frac{b}{c} \rfloor \rfloor \right)^2 = g(n, a \bmod c, b \bmod c, c)+2\lfloor \frac{a}{c} \rfloor h(n, a\bmod c, b \bmod c, c) + 2 \lfloor \frac{b}{c} \rfloor f(n, a \bmod c, b \bmod c, c) + s_2(n)\lfloor \frac{a}{c} \rfloor ^ 2 + n(n+1)\lfloor \frac{a}{c} \rfloor \lfloor \frac{b}{c} \rfloor + (n+1)\lfloor \frac{b}{c} \rfloor ^ 2 g ( n , a , b , c ) = i = 0 ∑ n ( ⌊ c ( a mod c ) i + b mod c + i ⌊ c a ⌋ + ⌊ c b ⌋⌋ ) 2 = g ( n , a mod c , b mod c , c ) + 2 ⌊ c a ⌋ h ( n , a mod c , b mod c , c ) + 2 ⌊ c b ⌋ f ( n , a mod c , b mod c , c ) + s 2 ( n ) ⌊ c a ⌋ 2 + n ( n + 1 ) ⌊ c a ⌋ ⌊ c b ⌋ + ( n + 1 ) ⌊ c b ⌋ 2
c > min { a , b } c > \min\{a, b\} c > min { a , b } x 2 = x ( x + 1 ) − x = 2 s 1 ( x ) − x x^2 = x(x+1)-x = 2s_1(x) - x x 2 = x ( x + 1 ) − x = 2 s 1 ( x ) − x m = ⌊ a n + b c ⌋ m=\lfloor \frac{an
+b}{c} \rfloor m = ⌊ c an + b ⌋ g ( n , a , b , c ) = ∑ i = 0 n ⌊ a i + b c 2 ⌋ = 2 ( ∑ i = 0 n ∑ j = 1 ⌊ a i + b c ⌋ j ) − ( ∑ i = 0 n ⌊ a i + b c ⌋ ) = 2 ( ∑ i = 0 n ∑ j = 0 m − 1 ( j + 1 ) [ j < ⌈ a i + b − c + 1 c ⌉ ] ) − f ( n , a , b , c ) = 2 ( ∑ j = 0 m − 1 ( j + 1 ) ∑ i = 0 n [ i > ⌊ c j − b + c − 1 a ⌋ ] ) − f ( n , a , b , c ) = 2 ( ∑ j = 0 m − 1 ( j + 1 ) ( n − ⌊ c j − b + c − 1 a ⌋ ) ) − f ( n , a , b , c ) = 2 n × s 1 ( m ) − 2 h ( m − 1 , c , c − b − 1 , a ) − 2 f ( m − 1 , c , c − b − 1 , a ) − f ( n , a , b , c ) \displaystyle g(n, a, b, c) = \sum_{i=0}^n \lfloor \frac{ai+b}{c}^2 \rfloor = 2\left(\sum_{i=0}^n \sum_{j=1}^{\lfloor \frac{ai+b}{c} \rfloor}j\right)-\left(\sum_{i=0}^n\lfloor \frac{ai+b}{c} \rfloor\right) = 2\left(\sum_{i=0}^n\sum_{j=0}^{m-1
} (j+1)[j < \lceil \frac{ai+b-c+1}{c} \rceil]\right) - f(n, a, b, c) = 2\left(\sum_{j=0}^{m-1
} (j+1) \sum_{i=0}^n [i > \lfloor \frac{cj-b+c-1}{a} \rfloor]\right) - f(n, a, b, c) = 2\left(\sum_{j=0}^{m-1
} (j+1) \left(n - \lfloor \frac{cj-b+c-1}{a} \rfloor\right)\right) - f(n, a, b, c) = 2n\times s_1(m) - 2h(m-1, c, c-b-1, a) - 2f(m-1, c, c-b-1, a) - f(n, a, b, c) g ( n , a , b , c ) = i = 0 ∑ n ⌊ c ai + b 2 ⌋ = 2 i = 0 ∑ n j = 1 ∑ ⌊ c ai + b ⌋ j − ( i = 0 ∑ n ⌊ c ai + b ⌋ ) = 2 ( i = 0 ∑ n j = 0 ∑ m − 1 ( j + 1 ) [ j < ⌈ c ai + b − c + 1 ⌉] ) − f ( n , a , b , c ) = 2 ( j = 0 ∑ m − 1 ( j + 1 ) i = 0 ∑ n [ i > ⌊ a c j − b + c − 1 ⌋] ) − f ( n , a , b , c ) = 2 ( j = 0 ∑ m − 1 ( j + 1 ) ( n − ⌊ a c j − b + c − 1 ⌋ ) ) − f ( n , a , b , c ) = 2 n × s 1 ( m ) − 2 h ( m − 1 , c , c − b − 1 , a ) − 2 f ( m − 1 , c , c − b − 1 , a ) − f ( n , a , b , c )
h h h
c ⩽ max { a , b } c \leqslant \max\{a, b\} c ⩽ max { a , b } h ( n , a , b , c ) = h ( n , a m o d c , b m o d c , c ) + s 1 ( n ) ⌊ b c ⌋ + s 2 ( n ) ⌊ a c ⌋ h(n, a, b, c) = h(n, a \bmod c, b \bmod c, c) + s_1(n) \lfloor \frac{b}{c} \rfloor + s_2(n) \lfloor \frac{a}{c} \rfloor h ( n , a , b , c ) = h ( n , a mod c , b mod c , c ) + s 1 ( n ) ⌊ c b ⌋ + s 2 ( n ) ⌊ c a ⌋ c > min { a , b } c > \min\{a, b\} c > min { a , b } h ( n , a , b , c ) = ∑ i = 0 n i ⌊ a i + b c ⌋ = ∑ i = 0 n i ∑ j = 0 m − 1 [ c j < a i + b − c + 1 ] = ∑ j = 0 m − 1 ∑ i = 0 n i [ i > ⌊ c j + c − b − 1 a ⌋ ] = ∑ j = 0 m − 1 ( s 1 ( n ) − ∑ i = 0 n i [ i ⩽ ⌊ c j + c − b − 1 a ⌋ ] ) = ∑ j = 0 m − 1 s 1 ( n ) − s 1 ( ⌊ c j + c − b − 1 a ⌋ ) = m × s 1 ( n ) − ∑ j = 0 m − 1 ( ⌊ c j + c − b − 1 a ⌋ 2 + ⌊ c j + c − b − 1 a ⌋ ) 2 = s 1 ( n ) × m − f ( m − 1 , c , c − b − 1 , a ) − g ( m − 1 , c , c − b − 1 , a ) \displaystyle h(n, a, b, c) = \sum_{i=0}^n i\lfloor \frac{ai+b}{c} \rfloor = \sum_{i=0}^ni\sum_{j=0}^{m-1}[cj < ai+b-c+1] = \sum_{j=0}^{m-1}\sum_{i=0}^ni[i > \lfloor \frac{cj+c-b-1}{a} \rfloor] = \sum_{j=0}^{m-1}\left(s_1(n)-\sum_{i=0}^n i[i \leqslant \lfloor \frac{cj+c-b-1}{a} \rfloor]\right) = \sum_{j=0}^{m-1} s_1(n)-s_1(\lfloor \frac{cj+c-b-1}{a} \rfloor) = m\times s_1(n)-\frac{\sum_{j=0}^{m-1}\left(\lfloor \frac{cj+c-b-1}{a} \rfloor^2+\lfloor \frac{cj+c-b-1}{a} \rfloor\right)}{2} = s_1(n)\times m - f(m-1, c, c-b-1, a) - g(m-1, c, c-b-1, a) h ( n , a , b , c ) = i = 0 ∑ n i ⌊ c ai + b ⌋ = i = 0 ∑ n i j = 0 ∑ m − 1 [ c j < ai + b − c + 1 ] = j = 0 ∑ m − 1 i = 0 ∑ n i [ i > ⌊ a c j + c − b − 1 ⌋] = j = 0 ∑ m − 1 ( s 1 ( n ) − i = 0 ∑ n i [ i ⩽ ⌊ a c j + c − b − 1 ⌋] ) = j = 0 ∑ m − 1 s 1 ( n ) − s 1 (⌊ a c j + c − b − 1 ⌋) = m × s 1 ( n ) − 2 ∑ j = 0 m − 1 ( ⌊ a c j + c − b − 1 ⌋ 2 + ⌊ a c j + c − b − 1 ⌋ ) = s 1 ( n ) × m − f ( m − 1 , c , c − b − 1 , a ) − g ( m − 1 , c , c − b − 1 , a )
考试给👴遇到了就下地狱吧。
最后的代码还是有点说头，很诡秘的是，用函数式取模会 T 飞，三个函数一起写会 Wa，反正最后的结局就是 modint+抄代码。
tpl floor_sum(LL n, int a, int b, int c) {
if (a == 0) {
return {mi(n+1)*(b/c), mi(n+1)*sqr(b/c), s(n)*(b/c)};
}
if (a >= c || b >= c) {
tpl ret = floor_sum(n, a%c, b%c, c);
return {
ret.f+s(n)*(a/c)+mi(n+1)*(b/c),
ret.g+mi(2)*(a/c)*ret.h+mi(2)*(b/c)*ret.f+s2(n)*sqr(a/c)+mi(2)*s(n)*(a/c)*(b/c)+mi(n+1)*sqr(b/c),
ret.h+s(n)*(b/c)+s2(n)*(a/c)
};
}
LL m = (a*n+b)/c;
tpl ret = floor_sum(m-1, c, c-b-1, a);
return {
mi(n)*m-ret.f,
mi(2)*n*s(m)-2*ret.h-2*ret.f-(mi(n)*m-ret.f),
s(n)*m-ret.f*iv2-ret.g*iv2
};
}
阶，原根，还有，，？
学数论，就好比吃shit。吃shit啊吃shit
阶 multiplicative order ：在 ( a , m ) = 1 (a, m) = 1 ( a , m ) = 1 a n ≡ 1 ( m o d m ) a ^ n \equiv 1 \pmod m a n ≡ 1 ( mod m ) n n n a a a m m m δ m ( a ) \delta_m(a) δ m ( a )
由于欧拉定理，所以阶一定存在（至少有一个 φ ( m ) \varphi(m) φ ( m )
{ 1 , a 2 , … , a δ m ( a ) − 1 } \{1, a^2, \dots, a^{\delta_m(a)}-1\} { 1 , a 2 , … , a δ m ( a ) − 1 } m m m
