笔记第二弹
Solidity
要求x比a的b次方最小
因为b在幂次上，
所以同样希望b最小
将x唯一分解
a,b一定是质数且b是x的最小智英淑
枚举每一个a的贡献，
然后枚举小于a的b
满足能整除b且整除于a的b次方的数
Empty up a Bottle
对于任意正整数
都有jie，-1的case并不存在
不妨设两个偶数一个奇数，
其他方案均可通过操作转移到这个状态
根据欧拉定理
2 t + 1 , 2 h 可以在 ϕ ( 2 t + 2 h ) 次下变成 2 t + h + 1 , h , 2t+1,2h可以在\phi(2t+2h)次下变成2t+h+1,h, 2t+1,2h可以在ϕ(2t+2h)次下变成2t+h+1,h,
https://www.luogu.com.cn/problem/P8457
首先构造一个n次方程的解
对n进行标准分解
n ϕ ( n ) 的所有素因子构成集合 S n\phi(n)的所有素因子构成集合S nϕ(n)的所有素因子构成集合S
对 1 < = y < = k 归纳构造 x 对1<=y<=k归纳构造x \\ 对1<=y<=k归纳构造x
使得 x x − − − p ( m o d x 1 ) 使得x^x---p(mod x_1) 使得xx−−−p(modx1)
考虑在模n的每一个质因数分解时的解，
则x与S中不超过pt的元素互素
其中
xi为
x i = p 1 a 1 ∗ p 2 a 2 ∗ . . . p i a i x_i=p_1^{a_1}*p_2^{a_2}*...p_i^{a_i} xi=p1a1∗p2a2∗...piai
（后面更不上了，讲的啥呀，听不清
https://loj.ac/p/3632
考虑g是完全积性函数
则
f d ( i j ) = g ( i ) g ( j ) f d ( i j ) 2 f_d(ij) = g(i)g(j)f_d(ij)^2 fd(ij)=g(i)g(j)fd(ij)2
设h(x)是满足
t d + 1 ∣ x t^{d+1}|x td+1∣x
的最大t
则
f d ( x ) 2 = [ h ( x ) = 1 ] = ∑ t d + 1 ∣ x μ ( t ) f_d(x)^2 = [h(x)=1] = \sum_{t^{d+1}|x}\mu(t) fd(x)2=[h(x)=1]=td+1∣x∑μ(t)
于是可以dsu on tree,合并的部分是:
g ( a ) [ t d + 1 / g c d ( t d + 1 , b ) ∣ a ] . g(a)[td+1/gcd(td+1,b)|a]. g(a)[td+1/gcd(td+1,b)∣a].
最后可以只考虑t|b是因为若不然则t>1且
t d + 1 ∣ a td+1|a td+1∣a
从而
f d ( a ) = 0 fd(a)=0 fd(a)=0
所以加入一个权值时需要枚举它的约束去算
更新贡献,但由于权值是排列,故总复杂度O(nlog2n).
https://loj.ac/p/6886
https://www.luogu.com.cn/problem/P9382
注意到挖掉一列对角线影响不大
考虑在每一组线性基中暴力查找
找到可能的值，然后记录
满足限制时，
只需对记录内容做一个背包即可
https://uoj.ac/problem/703
考虑所有数中选择线性基，
计算内表达数字的总个数
计算出后在取值中进行DP
求解lis
https://uoj.ac/problem/698
线性基求交：求两个空间的交的基。
也就是选出尽量多的、线性无关的、能被A,B同时表示出的数。
遍历Bi，能否被AU{B1,…,Bi−1}的子集异或
将此方案中属于A的子集的异或和加进交的基里。
正确性易证。
之后二分即可