Algorithm
Project Euler 429. Sum of squares of unitary divisors
A unitary divisor d of a number n is a divisor of n that has the property gcd(d, n/d) = 1.
The unitary divisors of 4! = 24 are 1, 3, 8 and 24.
The sum of their squares is 1^2 + 3^2 + 8^2 + 24^2 = 650.
Let S(n) represent the sum of the squares of the unitary divisors of n. Thus S(4!)=650.
Find S(100 000 000!) modulo 1 000 000 009.
分析
1 若n的因子分解是
prod.png
则它的unitary divisors是
unitary.png
其中c_i取值均为0或1.
所以 unitary divisors的平方和是
sum.png
2 要对n!因子分解，就是对于所有不大于n的质数p_i，求n!中含有多少个p_i因子.
factor.png
3 计算中经常做一下modulo吧
Python程序
from primesieve import primes
def factor_count(n: int, p: int):
s = 0
while n > 0:
n = n // p
s += n
return s
def power_mod(a: int, b: int, m: int):
if b == 0:
return 1
x = power_mod(a, b // 2, m)
x = x * x if b % 2 == 0 else x * x * a
return x % m
if __name__ == '__main__':
n, m = 100000000, 1000000009
s = 1
for p in primes(n):
s = s * (1 + power_mod(p, 2 * factor_count(n, p), m)) % m
if s == 0:
break
print(s)
耗时 10.323s
复杂度
prime sieve 求质数
n_log_log_n.png
遍历质数
pi_n.png
因子分解、求幂
n.png
因此整个算法的时间复杂度是
n_log_log_n.png
Review
The Unreasonable Effectiveness of SQL
SQL 由于其声明式的语法、对扩展开放、独立于数据存储，成为成功的4GL
即使是在NoSQL数据库，通常也会提供SQL语法支持。
Tip
https://github.com/romkatv/gitstatus/blob/master/docs/listdir.md
加速 list dir 到40%的技巧
Share
- 背景
- HTTP 诞生时都是文本页面
- 现在通常页面都有MB大小，一个页面需要发起数百个请求，HTTP 1 不再适用
- HTTP 1 的问题和 HTTP/2 的解法
- head of line blocking 同一个连接上的请求必须依次收到回复
- 同一个连接允许并发传输多个请求
- TCP 慢启动
- 复用TCP连接
- Headers 冗余
- Header 去重、压缩
- head of line blocking 同一个连接上的请求必须依次收到回复
- 概览
- HTTP/2是二进制传输
- 工作在TLS连接之上
- 一个TCP连接分为多个Stream，各处理一个HTTP请求
- 建立连接
- 建立TLS连接
- 通过ALPN来协商使用HTTP/2协议
- 客户端发送connection preface和SETTINGS帧
- 服务端发送SETTINGS帧
- HTTP/2 帧
- Lenghth: 24bits
- Type: 8bits
- SETTINGS
- HEADERS
- DATA
- Flags: 8bits
- R: 1bit
- Stream Id: 31bits
- Payload:
Lengthbits
- Stream
- HEADERS 帧开启新的Stream
- Headers需要多个帧时，后面用CONTINUATION帧，最后一帧的Flags打上END_HEADERS
- HEADERS 帧开启新的Stream
- Headers压缩
- 建立Lookup Table
- 其他特性
- 流控
- Stream优先级
- Server Push
