Codeforces数论专题
先搞了一波字符串，是时候到数论了。
2019.4.11
CF1070A Find a Number
用(i,j)表示数字和为i，余数为j的最短路，那么就是(0,0)到(s,0)的最短路。由于边权为1，直接bfs即可。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。代码就不写了。
CF1109E Sasha and a Very Easy Test
显然可以线段树，主要问题在于模数不为质数，可能不存在逆元。
那么可以把模数质因数分解一下，所有a除掉不互质的部分分别搞，剩下的就可以exgcd求逆元了。
exgcd写错调了半年……
CF1034C Region Separation
感觉好神仙啊……是我太菜了吗？
考虑如何判断分成k份是否可行。每一份权值和都是S/k，那么可以一个简单的dfs搞定：每次子树积到S/k就断开，看是否可行。
分析一下，可以看有多少个节点子树权值和为S/k的倍数，如果恰好有k个就可行。
又因为\(\frac{S}{k}|x\Leftrightarrow \frac{S}{\gcd(x,S)}|k\)，所以可以直接\(O(n\ln n)\)统计。
然后发现一个重要性质：若分\(t\)次，第\(t\)次分成了\(k_t\)份，那么当且仅当\(k_{t-1}|k_t\)时成立，且方法唯一。
所以再一次\(O(n\ln n)\)做\(dp_{xk}+=dp_k\)即可。
更多精彩
