摘要： CF2037G Natlan Exploring 题目简述 \[f_1=1 \]\[f_n=\sum_{i=1}^{n-1}\bigl[\gcd(a_i,a_n)\neq1\bigr]\cdot f_i \]已知 \(n\)，\(a_i\)，求 \(f_n\). 答案对 \(998244353\) 阅读全文

摘要： 洛谷 P4240 毒瘤之神的考验 题目简述 求 \[\sum_{i=1}^n\sum_{j=1}^m\varphi(ij) \]答案对 \(998244353\) 取模. 推导过程 默认本文中出现的 \(p\) 均为质数. 不妨设 \(n\leq m\). 首先，需要证明 \[\varphi(ab) 阅读全文

摘要： CF1575G GCD Festival 题目简述 求 \[\sum_{i=1}^n\sum_{j=1}^n\gcd(a_i,a_j)\cdot\gcd(i,j) \]其中 \(n\leq 10^5\)，\(a_i\leq 10^5\). 答案对 \(10^9+7\) 取模. 推导过程 \[\beg 阅读全文

摘要： 题目链接 题目简述 求 \[\sum_{i=1}^n\sum_{j=i+1}^n\gcd(i,j) \]推导过程 \[\begin{align*} &\sum_{i=1}^n\sum_{j=i+1}^n\gcd(i,j) \\ =\space&\frac{1}{2}\cdot\sum_{i=1}^n 阅读全文

摘要： 洛谷 P6156 简单题 题目简述 给出 \(n\)，\(k\)，求 \[\sum\limits_{i=1}^n\sum\limits_{j=1}^n(i+j)^kf(\gcd(i,j))\gcd(i,j) \]答案对 \(998244353\) 取模. \(f\) 函数定义如下： 如果 \(k\) 阅读全文

摘要： 定义申明 根节点的深度为 \(0\)。 一个节点的祖先和后代均包括自己。 C++ 代码仅供参考，毕竟代码风格因人而异。 引入 【模板】最近公共祖先（LCA） 首先要明确，树上任意两点均有公共祖先：根节点，所以 LCA 问题总是有解的。 直接跟着题意做，找出两个点的所有祖先，然后找它们的交集中与两点距 阅读全文