笔记第二弹

Solidity

要求x比a的b次方最小

因为b在幂次上，

所以同样希望b最小

将x唯一分解

a,b一定是质数且b是x的最小智英淑

枚举每一个a的贡献，

然后枚举小于a的b

满足能整除b且整除于a的b次方的数

Empty up a Bottle

对于任意正整数

都有jie，-1的case并不存在

不妨设两个偶数一个奇数，

其他方案均可通过操作转移到这个状态

根据欧拉定理

$$2t+1,2h可以在\varphi (2t+2h)次下变成2t+h+1,h,$$

https://www.luogu.com.cn/problem/P8457

首先构造一个n次方程的解

对n进行标准分解

$$n\varphi (n)的所有素因子构成集合S$$
$$对1<=y<=k归纳构造x$$
$$使得x^x---p(mod{x}_1)$$

考虑在模n的每一个质因数分解时的解，

则x与S中不超过pt的元素互素

其中

xi为

$$x_i=p_1^{a_1}\ast p_2^{a_2}\ast ...p_i^{a_i}$$

（后面更不上了，讲的啥呀，听不清

https://loj.ac/p/3632

考虑g是完全积性函数

则
$$f_d(ij)=g(i)g(j)f_d(ij{)}^2$$

设h(x)是满足

$$t^{d+1}|x$$

的最大t

则

$$f_d(x{)}^2=[h(x)=1]=\sum _{t^{d+1}|x}\mu (t)$$

于是可以dsu on tree,合并的部分是:
$$g(a)[td+1/gcd(td+1,b)|a].$$
最后可以只考虑t|b是因为若不然则t>1且
$$td+1|a$$
从而
$$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的子集的异或和加进交的基里。

正确性易证。

之后二分即可