死亡阴影之谷

OI

目录

[0] PE 464
[0] PE 303
[2-] PE 565

杂记 & 题解

2016.12.13 火曜日

原来的机房要被拆了……从我学OI到现在已经有3个机房惨遭黑手了……
身边物是人非，连机房都没了，我也快到了要离开的时候了……
到了晚上打开了一些不太对的歌单整个人画风都不对了……
也不知道我18岁的时候会在干什么……整个人都非常绝望。
最悲伤的是待了4年快要离开了也没留下来什么。
但也只能这样了，只能希望自己能再留下来一年了。

一边回忆一下开学来写的题一边写写新题吧。

PE 464

感觉在PE上出个裸树状数组也是挺厉害的。

考虑算不合法的方案数，显然只可能不符合两个条件中的一个，于是直接所有方案数减违反第一个限制减违反第二个限制的方案数就行了。
化成$100P_b-99N_b<100P_a-99N_a$就变成一个树状数组大暴力了……

PE 303

我的智力真的有点低啊……
直接$(i,(10i+d)\bmod n)$建边跑BFS不就好了……我是智障么……

def calc(n):
    print n
    last = [(-1, -1) for _ in xrange(n)]
    last[1] = (0, 1)
    last[2] = (0, 2)
    q = [1, 2]
    for u in q:
        vs = [(u * 10 + d) % n for d in xrange(3)]
        for d, v in enumerate(vs):
            if last[v][0] == -1:
                q.append(v)
                last[v] = (u, d)
    cur = 0
    ans = 0
    pow10 = 1
    while last[cur][0] != 0:
        v, d = last[cur]
        ans = ans + d * pow10
        pow10 = pow10 * 10
        cur = v
    return ans + pow10 * cur
res = 2
for i in xrange(3, 10001):
    res += calc(i)
print res

PE 565

智力低到爆炸……
显然是直接算所有$\sigma(p^k)\bmod 2017=0$的贡献。
$k>1$的情况可以直接暴力，$k=1$的话需要素数筛。

考虑如果$2017p-1$是合数，那么考虑$p$的一个素因子$d$，有$2017p\equiv 1\pmod{d}$，也就是$p=kd+r$，其中$2017r\equiv 1\pmod{d}$。

然后就变成埃氏筛了……

我居然写了一个miller-rabin大暴力就上了……真的是……

不包括数论板子的暴力

m = 10 ** 11
ans = 0
cur = 4033
valid = []
while cur < m:
    not_prime = False
    for d in _known_primes:
        if cur % d == 0:
            not_prime = True
            break
    if (not not_prime) and is_prime(cur):
        valid.append(cur)
        t = m // cur
        ans += cur * (1 + t) * t / 2
        if cur * cur <= m:
            tt = m // (cur * cur)
            ans -= cur * cur * (1 + tt) * tt / 2
    cur += 4034
for i in prime_list:
    val = i * i
    sigma = (1 + i + i * i) % 2017
    while val <= m:
        if sigma == 0:
            valid.append(val)
            t = m // val
            ans += val * (1 + t) * t / 2
            if val * i <= m:
                print val * i
                tt = m // (val * i)
                ans -= val * i * (1 + tt) * tt / 2
        val *= i
        sigma = (sigma + val) % 2017
valid = sorted(valid)
for i in valid:
    for j in valid:
        if i * j > m:
            break
        if (j < i) and (i % j != 0):
            t = m // (i * j)
            ans -= i * j * (1 + t) * t / 2
print ans

2016.12.27 火曜日

难过……
在各种地方被各种各样的人虐……
记得自己一直以来也都是这样……
无论是在逃避还是在面对……
事实并没有改变啊……
我到底在干嘛啊……

CF484C Strange Sorting

从第$i-1$步到第$i$步的转移可以看成一个置换……
快速幂就行了……

CF487C Prefix Product Sequence

……
$a_i=\frac{i}{i-1}$

CF487D Conveyor Belts

分块……

CF487E Tourists

点双树上树剖……