P4571 [JSOI2009] 瓶子和燃料
先对两个容量分别为 \(a\)，\(b\) 的瓶子考虑。
可以发现，无论是倒入还是倒出，体积都是 \(a\) 或 \(b\) 的整数倍。
因此可以考虑求 \(ax+by\) 的最小正整数解。
由裴蜀定理可得，最小正整数解为 \(\gcd(a,b)\)。
因此，原问题转化为从 \(n\) 个数中选择 \(k\) 个数，使它们的 \(\gcd\) 最大。
P2480 [SDOI2010]古代猪文
求
\[g^{\sum_{d\mid n}\binom{n}{d}}\bmod 999911659 \]由扩展欧拉定理转化，相当于需要求
\[\sum_{d\mid n}\binom{n}{d}\bmod 999911658 \]把 \(999911658\) 分解质因数得 \(999911658= 2\times 3\times 4679\times 35617\)，用 Lucas 定理计算出组合数，再用 CRT 合并即可。
P4593 [TJOI2018]教科书般的亵渎
\(k=m+1\)。
令 \(S(n)=\sum_{i=1}^ni^k\)。
答案为
\[\sum_{i=0}^{m}\sum_{j=i+1}^{m+1}S(a_j-a_{i}-1)-S(a_{j-1}-a_{i}) \]\(S(n)\) 是一个 \(m+2\) 次多项式，因此可以拉格朗日插值。
复杂度为 \(O(m^4)\)。
P2183 [国家集训队]礼物
答案为
\[\frac{n!}{(n-\sum_{i=1}^mw_i)\prod_{i=1}^mw_i!} \]使用类似 exLucas 的方法求解即可。
P1829 [国家集训队]Crash的数字表格 / JZPTAB
\[\begin{aligned} \sum_{i=1}^n\sum_{j=1}^mlcm(i,j)&=\sum_{d=1}^{\min(n,m)}\frac{1}{d}\sum_{i=1}^n\sum_{j=1}^mi\cdot j[\gcd(i,j)=d]\\ &=\sum_{d=1}^{\min(n,m)}d\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}i\cdot j[\gcd(i,j)=1]\\ \end{aligned} \]记 \(S(n,m)=\sum_{i=1}^n\sum_{j=1}^mi\cdot j[\gcd(i,j)=1]\)。
\[ S(n,m)=\sum_{i=1}^n\sum_{j=1}^mi\cdot j\sum_{(d|i),(d\mid j)}\mu(d) \]\[=\sum_{d=1}^{\min(n,m)}\mu(d)d^2\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}i\cdot j \]令 \(F(n,m)=\sum_{i=1}^n\sum_{j=1}^mi\cdot j\)。
\[\begin{aligned} F(n,m)&=\sum_{i=1}^ni\frac{m(m+1)}{2}\\ &=\frac{n(n+1)m(m+1)}{4} \end{aligned} \]所以
\[S(n,m)=\sum_{d=1}^{\min(n,m)}\mu(d)d^2\frac{\lfloor\frac{n}{d}\rfloor(\lfloor\frac{n}{d}\rfloor+1)\lfloor\frac{m}{d}\rfloor(\lfloor\frac{m}{d}\rfloor+1)}{4} \]使用整除分块，求解 \(S(n,m)\) 的复杂度为 \(O(\sqrt n)\)。
而求解答案需要算 \(O(\sqrt n)\) 次 \(S\) 函数。
因此总复杂度为 \(O(n)\)。
P3704 [SDOI2017]数字表格
设答案为 \(F(n,m)\)。
令 \(G(n,m)=\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=1]\)
\[\begin{aligned} F(n,m)&=\prod_{i=1}^n\prod_{j=1}^mf_{\gcd(i,j)}\\ &=\prod_{d=1}^{\min(n,m)}f_d^{G(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)} \end{aligned} \]类似上一题的推导
\[G(n,m)=\sum_{i=1}^n\sum_{j=1}^m\sum_{(d\mid i),(d\mid j)}\mu(d) \]\[=\sum_{d=1}^{\min(n,m)}\mu(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor \]\(O(\sqrt n)\) 可以求得 \(G(n,m)\)。
对 \(F(n,m)\) 也整除分块即可做到 \(O(n)\)。
但是，这道题有 \(10^3\) 组数据，运算量达到 \(10^9\)，似乎不能通过。
考虑把 \(G\) 带回 \(F\)。
不妨设 \(n < m\)。
\[\begin{aligned} F(n,m)&=\prod_{d=1}^nf_d^{\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\mu(i)\lfloor\frac{n}{id}\rfloor\lfloor\frac{m}{id}\rfloor}\\ &=\prod_{i=1}^n\prod_{d=1}^{\lfloor\frac{n}{i}\rfloor}f_d^{\mu(i)\lfloor\frac{n}{id}\rfloor\lfloor\frac{m}{id}\rfloor}\\ &=\prod_{T=1}^n\left(\prod_{d\mid T}f_d^{\mu(\frac{T}{d})}\right)^{\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor} \end{aligned} \]内层是调和级数均摊 \(O(n\log n)\)，因此总时间复杂度为 \(O(n\log n+T\sqrt n\log n)\)。
需要注意的是指数不能随便取模。
CF1106F Lunar New Year and a Recursive Sequence
递推式为乘积的形式，不好处理，但如果用原根表示每个数，令 \(G^{g_i}\equiv f_i\pmod{998244353}\) 递推式就为相加的形式了。
即 \(G^{g_i}=\prod_{j=1}^kG^{g_{i-j}b_j}\)，其中，\(G\) 为模 \(998244353\) 意义下的原根。
那么，\(g_i=\sum_{j=1}^kb_jg_{i-j}\)，在模 \(998244352\) 下进行。
对它矩阵快速幂可以得到一个方程 \(g_kx\equiv g_n\pmod{998244352}\)。
其中，\(G^{g_n}\equiv m\pmod{998244353}\)，这可以通过 BSGS 求解。
可以通过 \(g_n\) 得到 \(g_k\)，解出 \(g_k\) 后即可得到
CF645F Cowslip Collections
莫比乌斯反演的倍数形式。
设 \(cnt_i\) 表示含有因子 \(i\) 的数的个数。
\(F(i)\) 表示 \(\gcd\) 为 \(i\) 的倍数的方案数。
\(F(i)=\binom{cnt_i}{k}\)。
\(f(i)\) 表示 \(\gcd\) 为 \(i\) 的方案数。
由莫比乌斯反演，得 \(f(i)=\sum_{i\mid t}F(t)\mu(\frac{t}{i})=\sum_{i\mid t}\binom{cnt_t}{k}\mu(\frac{t}{i})\)。
设 \(m\) 为最大的数，于是答案为 \(\sum_{i=1}^mif(i)=\sum_{i=1}^mi\sum_{i\mid t}\binom{cnt_t}{k}\mu(\frac{t}{i})\)
每次更新会使得某个 \(cnt\) 加 \(1\)，它会对所有整除它的数产生贡献。
假设 \(t\) 的出现次数加 \(1\)，那么新增贡献为 \(\sum_{d\mid t}d\mu(\frac{t}{d})(\binom{cnt_t+1}{k}-\binom{cnt_t}{k})=\varphi(t)(\binom{cnt_t+1}{k}-\binom{cnt_t}{k})\)。
P4240 毒瘤之神的考验
不妨 \(n<m\)。
\[\begin{aligned} Ans&=\sum_{i=1}^n\sum_{j=1}^m\varphi(i,j)\\ &=\sum_{i=1}^n\sum_{j=1}^m\frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))}\\ &=\sum_{d=1}^n\frac{d}{\varphi(d)}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\varphi(id)\varphi(jd)[\gcd(i,j)=1]\\ &=\sum_{d=1}^n\frac{d}{\varphi(d)}\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)\sum_{i=1}^{\lfloor\frac{n}{kd}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{kd}\rfloor}\varphi(ikd)\varphi(jkd)\\ &=\sum_{d=1}^n\frac{d}{\varphi(d)}\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)\left(\sum_{i=1}^{\lfloor\frac{n}{kd}\rfloor}\varphi(ikd)\right)\left(\sum_{j=1}^{\lfloor\frac{m}{kd}\rfloor}\varphi(jkd)\right)\\ &=\sum_{T=1}^n\left(\sum_{k\mid T}\frac{\mu(k)T}{k\varphi(\frac{T}{k})}\right)\left(\sum_{i=1}^{\lfloor\frac{n}{T}\rfloor}\varphi(iT)\right)\left(\sum_{j=1}^{\lfloor\frac{m}{T}\rfloor}\varphi(jT)\right) \end{aligned} \]令 \(F(T)=\sum_{k\mid T}\frac{\mu(k)T}{k\varphi(\frac{T}{k})}\)，这个可以 \(O(n\log n)\) 预处理。
令 \(G(T,n)=\sum_{i=1}^n\varphi(iT)\)，这也可以 \(O(n\log n)\) 预处理。
于是
\[Ans=\sum_{T=1}^nF(T)G(T,\lfloor\frac{n}{T}\rfloor)G(T,\lfloor\frac{m}{T}\rfloor) \]发现这并不能整除分块。
于是预处理 \(H(n,a,b)=\sum_{T=1}^nF(T)G(T,a)G(T,b)\)。
直接预处理会 TLE + MLE，考虑分块。
发现当 \(\frac{n}{T}\) 越小时整除分块效率越高，于是可以设置一个阈值 \(B\)，\(a,b\leq B\) 的预处理，\(>B\) 的暴力计算。
总时间复杂度为 \(O(n\log n+nB^2+T(\sqrt n + \frac{n}{B}))\)。
P4619 [SDOI2018]旧试题
\[\begin{aligned} Ans &=\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^Cd(ijk)\\ &=\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^C\sum_{u\mid i}\sum_{v\mid j}\sum_{w\mid k}[\gcd(u,v)=1][\gcd(u,w)=1][\gcd(v,w)=1]\\ &=\sum_{i=1}^A\lfloor\frac{A}{i}\rfloor\sum_{j=1}^B\lfloor\frac{B}{j}\rfloor\sum_{k=1}^C\lfloor\frac{C}{k}\rfloor[\gcd(i,j)=1][\gcd(i,k)=1][\gcd(j,k)=1]\\ &=\sum_{u=1}^{\min(A,B)}\mu(u)\sum_{v=1}^{\min(A,C)}\mu(v)\sum_{w=1}^{\min(B,C)}\mu(w)\sum_{lcm(u,v)\mid i}\lfloor\frac{A}{i}\rfloor\sum_{lcm(u,w)\mid j}\lfloor\frac{B}{j}\rfloor\sum_{lcm(v,w)\mid k}\lfloor\frac{C}{k}\rfloor \end{aligned} \]令 \(F(x,n)=\sum_{x\mid t}\lfloor\frac{n}{t}\rfloor\)，\(O(n\log n)\) 预处理出 \(F(i,A/B/C)\)。
令 \(n=\max(A,B,C)\)。
\[Ans =\sum_{u=1}^{n}\mu(u)\sum_{v=1}^{n}\mu(v)\sum_{w=1}^{n}\mu(w)F(lcm(u,v),A)F(lcm(u,w),B)F(lcm(v,w),C) \]发现暴力枚举会达到 \(O(n^3\log n)\)，于是考虑换一种方式。
发现 \(u\)，\(v\)，\(w\) 可以是图上的三元环，且 \(\mu\) 很多情况是 \(0\)，也就是说边数很少，于是可以通过枚举三元环通过此题。
P3768 简单的数学题
\[Ans=\sum_{i=1}^n\sum_{j=1}^nij\gcd(i,j) \]\[=\sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^nijd[\gcd(i,j)=d] \]\[=\sum_{d=1}^n\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}ijd^3[\gcd(i,j)=1] \]\[=\sum_{d=1}^nd^3\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}ij\sum_{k\mid i, k\mid j}\mu(k) \]\[=\sum_{d=1}^nd^3\sum_{k=1}^n\mu(k)k^2S_1(\lfloor\frac{n}{dk}\rfloor)^2 \]\[=\sum_{T=1}^nS_1(\lfloor\frac{n}{T}\rfloor)^2T^2\sum_{d\mid T}d\mu(\frac{T}{d}) \]\[=\sum_{i=1}^nS_1(\lfloor\frac{n}{i}\rfloor)^2i^2\varphi(i) \]由杜教筛，构造 \(g(n)=n^2\)，则
\[S(n)=\sum_{i=1}^nn^3-\sum_{d=2}^nd^2S(\lfloor\frac{n}{d}\rfloor) \]CF1614D2 Divan and Kostomuksha
设 \(num_i\) 表示 \(a\) 中能被 \(i\) 整除的数的个数。
对于一段序列，它的前缀的 \(\gcd\) 一定是单调不增的，因此可以考虑从值大的往值小的考虑。
\(f_i\) 表示 \(\gcd\) 以 \(i\) 结尾的最大贡献。
\[f_i=\max_{i\mid j}f_j+(num_i-num_j)\cdot i \] 标签：lfloor,frac,04,省选,sum,mid,rfloor,mu,数论 From： https://www.cnblogs.com/yanchengzhi/p/17002019.html