所有题目都可以在 luogu 上找到.
1. [Celeste-B]Golden Feather
题意:
- 给定点 \(1,2,\cdots,n\), 点 \(k\) 的点权 \(w_k=k(k+2)\), 边权 \(d(x,y)=\gcd(w_x,w_y)\).
- 求这个完全图的最小生成树的边权和.
- 数据范围 \(1\leqslant n\leqslant10^{18}\).
评价: 离谱题.
结论: \(n=4\) 时答案为 \(5\), \(n=10\) 时答案为 \(11\), 剩余情况答案为 \(n-1\).
证明的话情况过于复杂, 不写了.
2. 签到题
题意: 求 \(\sum\limits_{k=l}^r(k-\varphi(k))\bmod 666623333\), \(1\leqslant l\leqslant r\leqslant10^{12}, r-l\leqslant10^6\).
区间筛出来素数然后用积性函数的性质随便搞搞就做完了(
3. [Violet]樱花
题意: 求不定方程 \(\dfrac{1}{x}+\dfrac{1}{y}=\dfrac{1}{n!}\) 的正整数解组数. \(1\leqslant n\leqslant 10^6.\)
套路题, 随便化一下即有 \((x-n!)(y-n!)=(n!)^2\), 右边是经典的阶乘质因数分解, 然后用约数个数公式就完事了.
4. The Neutral Zone
题意:
- 定义 \(\text{exlog}_f(p_1^{a_1}\cdots p_k^{a_k})=a_1f(p_1)+\cdots+a_kf(p_k), f(x)=Ax^3+Bx^2+Cx+D\).
- 求 \(\sum_ {i=1}^n\text{exlog}_f(i)\).
- 数据范围 \(1\leqslant n\leqslant3\times10^8, 0\leqslant A,B,C,D\leqslant10^6\), 空间限制 \(18\text{MiB}\).
显然那个式子就是 \(\text{exlog}_f(n!)\), 然后阶乘质因数分解就......做完了?
注意空间限制. \(3\times10^8\) 的数组根本存不下.
但是我们使用传统艺能区间筛, 只开 \(O(\sqrt{n})\) 的空间, 剩下的边算边计入答案就做完了.
5. 因子和
题意: 求 \(\sigma(a^b)\bmod 9901\), \(0\leqslant a,b\leqslant 5\times10^7\).
分解质因数套个公式得答案为 \(\prod\dfrac{p_k^{c_k+1}-1}{p_k-1}\). 但是你发现这个模数太小了逆元可能不存在.
两种处理方法. 一种是注意到逆元不存在时 \(p_k\bmod9901=1\), 于是直接得到上面式子的值.
另一种方法是完全不依赖于逆元, 分治求出等比数列和.
具体地, 记 \(S_n=1+p+\cdots+p^n\), 当 \(n\bmod2=1\) 时有 \(S_n=(1+p^{\lceil n/2\rceil})S_{\lfloor n/2\rfloor}\). \(n\bmod2=0\) 同理.
6. [SDOI2008] 沙拉公主的困惑
题意: 求 \([1,N!]\) 中和 \(M!\) 互质的数的个数. 数据范围 \(1\leqslant M\leqslant N\leqslant 10^7\).
我们发现 \(M!|N!\), 并且答案显然为 \(\dfrac{N!}{M!}\varphi(M!)=N!\dfrac{\prod(p_k-1)}{\prod p_k}\).
然后就能算了, 注意模数还是可能很小, 分子分母算答案的时候不要把模数乘上.
7. [PA2011]Prime prime power 质数的质数次方
题意: 对于给定的数 \(n\), 求第 \(k\) 小的 \(a^b\) (\(a,b\) 都为质数), 使得它的值大于 \(n\). \(1\leqslant n\leqslant 10^{18}, 1\leqslant k\leqslant10^5\).
8. 「MCOI-02」Convex Hull 凸包
题意: 计算 \(\sum\limits_{i=1}^n\sum\limits_{j=1}^m\tau(i)\tau(j)\tau(\gcd(i,j))\), \(1\leqslant n,m\leqslant 2\times10^6,1 \leqslant p\leqslant 10^9\).
用不着莫反.
9. [POI2012]ROZ-Fibonacci Representation
题意: 给一个 \(10^{17}\) 以内的数，问最少可以用几个斐波那契数加加减减凑出来.
简单题.
10. [NOIP2005 普及组] 循环
11. 圆点
题意: 求 \(\sum\limits_{x=0}^{\sqrt{R}}\sum\limits_{y=0}^{\sqrt{R}}[x^2+y^2\leqslant R]\). \(R\leqslant 10^{14}\).
还是简单题.
12. [HAOI2008]圆上的整点
题意: 求一个给定的圆 \(x^2+y^2=r^2\) 在圆周上有多少个点的坐标是整数. (\(r\leqslant 2\times10^9\))
结论题.
13. PRIMES2 - Printing some primes (Hard)
题意: 求出所有小于 \(10^9\) 的质数.
埃氏筛优化, Wheel Factorization. 前面 The Neutral Zone 那题就有类似思想.