一眼莫反
推式子的步骤就不写了，反正也比较套路
这里只给出最后的式子为：
A
n
s
=
∑
i
=
1
V
ϕ
(
i
)
∗
(
∑
i
∣
j
c
n
t
j
k
)
Ans=\sum\limits_{i=1}^{V}\phi(i)*\binom{\sum\limits_{i\mid j}cnt_j}{k}
Ans=i=1∑Vϕ(i)∗(ki∣j∑cntj)，其中
c
n
t
j
cnt_j
cntj 为数字
j
j
j 的出现次数
修改操作的话，根据式子，不难得出只要修改
x
x
x 的因子即可
时间复杂度
O
(
q
n
)
O(q\sqrt n)
O(qn)
#include 翻译有误！！！
显然我们的问题是要求出这棵树分成
k
k
k 个部分是否可行，如果可行，令
f
k
=
1
f_k=1
fk=1
那么只要做一遍
d
p
dp
dp，即可，式子为
f
i
=
∑
i
∣
j
f
j
f_i=\sum\limits_{i|j}f_j
fi=i∣j∑fj，注意
i
,
j
i,j
i,j 一定要是可行的
考虑如何求
f
k
f_k
fk
我们先求一遍子树和，令权值总和为
S
S
S，那么需要割的边即为满足
S
k
∣
s
i
\frac{S}{k}|s_i
kS∣si 的子树和
我们需要判断需要割的边的个数是否
=
k
=k
=k
考虑如何快速求解上面的问题
s
i
=
a
S
k
s_i=a\frac{S}{k}
si=akS
则
k
=
a
S
s
i
k=a\frac{S}{s_i}
k=asiS
所以说如果
k
k
k 是
S
(
S
,
s
i
)
\frac{S}{(S,s_i)}
(S,si)S 的倍数，那么
i
i
i 就会对
k
k
k 产生贡献，直接扫一遍
S
(
S
,
s
i
)
\frac{S}{(S,s_i)}
(S,si)S 在
n
n
n 以内的倍数即可
时间复杂度
O
(
n
ln
n
)
O(n\ln n)
O(nlnn)
#include 首先可以发现当
k
≤
l
o
g
2
n
k\le log_2^n
k≤log2n 时，答案一定为
n
n
n，因为可以按照二进制的位数分组，然后每组的
c
c
c 都为
1
1
1
现在只需要考虑
k
≤
16
k\le 16
k≤16 的情况
我们令
f
i
,
j
f_{i,j}
fi,j 为到
j
j
j 分成
i
i
i 段的最小值
看题解发现
f
i
,
j
f_{i,j}
fi,j 对于每一层的
i
i
i 满足决策单调性，所以可以直接分治解决
现在的问题是快速算出
c
(
l
,
r
)
c(l,r)
c(l,r)
推式子
.
.
.
...
...
自己在草稿纸上推可以得出
c
(
l
,
r
)
=
∑
i
=
l
r
∑
j
=
1
⌊
r
i
⌋
ϕ
(
j
)
c(l,r)=\sum\limits_{i=l}^r\sum\limits_{j=1}^{\lfloor\frac{r}{i}\rfloor}\phi(j)
c(l,r)=i=l∑rj=1∑⌊ir⌋ϕ(j)
发现这很分块
具体来说的话可以算出
ϕ
\phi
ϕ 的前缀和，然后分类讨论，和累加
感觉是道挺妙的题，但不太好讲，自己去看题解吧，讲的挺详细的
时间复杂度
O
(
16
n
l
o
g
n
)
O(16nlogn)
O(16nlogn)
#include 点击打开链接
感觉是一道很妙的题！！！反正我是完全没思路
考虑题目中的和限制与或限制有很好的对称性，那么不难发现 a 1 a_1 a1 的位置可以换到其他任何位置上，那么当 n n n 为偶数的时候答案即为 0 0 0，当 n n n 为奇数的时候答案为所有情况下 a 1 a_1 a1 的异或和（因为异或可以抵消，且 a 1 a_1 a1 可以换到任何一个位置，那么当 n n n 为奇数时一定只会剩下一个位置未被抵消）
首先一个朴素的想法是对
a
1
a_1
a1 分位计算，那么现在我们需要求当
2
i
⊆
a
1
2^i\subseteq a_1
2i⊆a1 的满足条件的方案数的奇偶性
对于 或 操作，具有比较好的性质（只有可能从
0
0
0 变为
1
1
1），所以我们考虑容斥求解
令
f
y
′
(
y
′
⊆
y
)
f_{y'}(y'\subseteq y)
fy′(y′⊆y) 为
∀
a
i
⊆
y
′
\forall a_i\subseteq y'
∀ai⊆y′ 且
∑
a
i
=
x
\sum a_i=x
∑ai=x 的方案数
所以方案数即为
∑
y
′
⊆
y
(
−
1
)
∣
y
∣
−
∣
y
′
∣
f
y
′
\sum\limits_{y'\subseteq y}(-1)^{|y|-|y'|}f_{y'}
y′⊆y∑(−1)∣y∣−∣y′∣fy′
因为我们只关心奇偶性，所以方案数可化简为
∑
y
′
⊆
y
f
y
′
\sum\limits_{y'\subseteq y}f_{y'}
y′⊆y∑fy′
需要满足
a
i
⊆
y
′
a_i\subseteq y'
ai⊆y′ 的条件不好办，所以我们考虑组合数逆用，可得
a
i
⊆
y
′
⟺
(
y
′
a
i
)
(
m
o
d
2
)
a_i\subseteq y'\iff \binom{y'}{a_i}(\mod 2)
ai⊆y′⟺(aiy′)(mod2)
把
f
y
′
f_{y'}
fy′ 拆分开来即为
∑
∑
a
i
=
x
−
2
i
(
y
−
2
i
a
1
)
(
y
a
2
)
.
.
.
(
y
a
n
)
\sum\limits_{\sum a_i=x-2^i}\binom{y-2^i}{a_1}\binom{y}{a_2}...\binom{y}{a_n}
∑ai=x−2i∑(a1y−2i)(a2y)...(any)
用范德蒙德卷积化简可得
(
n
y
−
2
i
x
−
2
i
)
(
m
o
d
2
)
=
[
(
x
−
2
i
)
⊆
(
n
y
−
2
i
)
]
\binom{ny-2^i}{x-2^i}(\mod 2)\\=[(x-2^i)\subseteq(ny-2^i)]
(x−2iny−2i)(mod2)=[(x−2i)⊆(ny−2i)]
直接计算即可
时间复杂度
O
(
y
l
o
g
y
)
O(ylogy)
O(ylogy)
#include 还是一道很妙的题！！！可能是我太菜了
我们一开始把所有数都选入集合中，然后考虑删数使两个集合的
l
c
m
lcm
lcm 相等
这个直接暴力查找删除即可，即找到
a
i
∤
∏
b
j
a_i\nmid \prod b_j
ai∤∏bj，
b
j
b_j
bj 是仍在答案集合中的
一个判断
a
i
∤
∏
b
j
a_i\nmid \prod b_j
ai∤∏bj 的直观想法是质因数分解，然后看次幂，但是
a
i
,
b
i
≤
4
∗
1
0
36
a_i,b_i\le 4*10^{36}
ai,bi≤4∗1036，明显不够做任何的质因数分解算法（
p
o
l
l
a
r
d
−
r
h
o
pollard-rho
pollard−rho 也跑不了）
所以考虑换一个角度思考问题
这里有一个很妙的判断方法是
gcd
(
a
gcd
(
a
,
b
1
)
,
a
gcd
(
a
,
b
2
)
,
.
.
.
,
a
gcd
(
a
,
b
k
)
)
\gcd(\frac{a}{\gcd(a,b_1)},\frac{a}{\gcd(a,b_2)},...,\frac{a}{\gcd(a,b_k)})
gcd(gcd(a,b1)a,gcd(a,b2)a,...,gcd(a,bk)a)，
k
k
k 为仍在答案集合中的数的个数，上面这个式子分类讨论然后自己分析一下不难理解
因为
gcd
\gcd
gcd 是可合并的，且需要支持修改，所以考虑用线段树维护
考虑每次删除数只会修改另一个序列中的当前位置，所以线段树只会修改
O
(
n
2
)
O(n^2)
O(n2) 次，删除数的话直接把
gcd
\gcd
gcd 赋为
0
0
0 即可，因为
gcd
(
x
,
0
)
=
x
\gcd(x,0)=x
gcd(x,0)=x
时间复杂度为
O
(
n
2
l
o
g
n
l
o
g
V
)
O(n^2lognlogV)
O(n2lognlogV)
#include 挺有意思的一道题（感觉十分多合一）
首先考虑到只有
k
k
k 的质因子是有用的，因为合数因子一定可以表示成多个质因子相加
那么现在的问题变成了询问
n
n
n 是否是
p
1
,
.
.
.
,
p
m
p_1,...,p_m
p1,...,pm 的线性组合，且每一项的系数需要非负
线性组合且非负，我们第一个想到的问题应该是 P3403 跳楼机，所以这道题我们可以套用那道题的做法，用同余最短路做
但我们发现
p
i
p_i
pi 很大，最小的
p
i
p_i
pi 甚至都不能做最短路，所以我们考虑分类讨论：
我是直接暴力质因数分解的（当然要先筛出质数），也可以过
因为是多合一做法，所以时间复杂度需要一个一个单独算，我就不算了，反正可以过
#include