问题为： \begin{align*} 若k != 1\ g(p) &= p^k-p^{k-1}-(p^{k-1}-p^{k-2})\\ g(p) &= p^k-2p^{k-1}+p^{k-2}\\ g(p) &= (p-1)^2p^{k-2}\\ \end{align*}这样的话就可以用线性筛递推求得g(n)#include <bits/stdc++.h> const int...
题目链接：https://loj.ac/problem/2000到这里为止时间复杂度显然是$O(TN^{2})$可以获得30分。那要AC我们就得继续对上式进行变形。设$i=dk$并带入下式并变形得显然这个表达式可以O(NlogN)的求出前缀积。然后我们根据这个表达式的性质再使用整数分块，然后就可以在$O(T\sqrt{N}logN)$内求出答案。代码：#include <bits/st...
整除分块在数论中经常会出现如下表达式：显然我们直接计算的时间复杂度为$O(N)$，于是我们需要一种拥有更优时间复杂度的算法。通过打表我们可以发现。改表达式具有一些特殊的性质。1.$\lfloor \frac{N}{i} \rfloor$最多只有$2\sqrt{N}$种取值证明:对于$i\leq\sqrt{N}$,只有$\sqrt{N}$种取值，对于$\sqrt{N}$,同样也只有$\sqrt...
二十四点夏威夷手算答案，然后让我从890开始交，然后到891就过了,嘿嘿嘿，我觉得我还挺欧的，夏威夷真的牛逼,讲题的时候jls对他竖起了大拇指说了句牛逼#include <bits/stdc++.h> using namespace std; int main() { int n; scanf("%d",&n); if(n ...
欧几里德算法又称辗转相除法，是指用于计算两个正整数a，b的最大公约数。算法描述：所以如果z如果是x，y的因子，则z一定是y-x的公因子，所以可以发现换成数学表述形式就是$gcd(a,b) = gcd(b,a\%b)$代码实现：int gcd(int a,int b){ if(b == 0) return a; else return gcd(b,a%b); }拓展欧几里得算法...