一行超人

最近两天集训数论题完全不会，根本不知道从哪里下手。看来还是姿势水平不够啊。

这里就把见过的姿势和技巧都记录一下把

有些东西看起来计算过程很复杂，这时候可以先打个表。有可能就发现规律了。比什么都来得快。还有一些看起来不太可做的题目，说不定也是有规律的。

要敢于猜结论，学会类比。比如众所周知的有$$\sum_{i=1}^{n}f(i)=\sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloor$$

然而$$\sum_{i=1}^{n}\sum_{j=1}^{m}f(i×j)$$也有类似的结论

$$\sum_{i=1}^{n}\sum_{j=1}^{m}f(i×j)=\sum_{i=1}^{n}\sum_{j=1}^{m}\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloor[gcd(i,j)==1]$$

三维的也是类似的 其中$f(n)$表示$n$的约数的个数

证明什么的打个表就好了 考场上哪想那么多

今天做去年清华集训的Sum，看题解的时候忽然领悟到一个神奇的东西。

有时候我们经常把一个条件转化成一个式子，直接求和就好了。

比方说判断某个数$x$是不是偶数，$x-2×\lfloor\frac{x}{2}\rfloor$ 就是答案。是偶数返回$1$，否则返回$0$

判断 $n\%k+m\%k>=k$是否成立，$\lfloor\frac{n+m}{k}\rfloor-\lfloor\frac{n}{k}\rfloor-\lfloor\frac{n}{k}\rfloor$就是答案。满足条件返回$1$，否则返回$0$

判断一个数$x$是否$=1$，$\sum_{i|x}μ(i)$就是我们要的结果

如果程序中有一个$if$语句显然不能很方便的求，但是我们要是变一下形式，把是否满足条件变成一个式子。所有的值都一视同仁直接暴力求和就好了。这样会让题目得到很大程度上的化简。

看做了3601又领悟了一些技巧

$$\sum_{i=1}^{n}i^d $$一定可以写成$$\sum_{i=1}^{d+1}a_i×n^i$$至于$a_i$是多少我们可以暴力求出前$d+1$个值然后高斯消元一发

还有就是某些式子的求和我们可以将它看成函数，然后如果是积性函数的话就可以只考虑质数然后乘起来了。（当然3061的最后一步直接DP好像也是可以的

BZOJ4174

戳题解 POPOQQQ大爷是厉害

这题为啥能做呢？为啥不适用类欧几里得呢？

因为我们要注意到后面那个$k$的循环是从$0-m-1$的。所以这一定有鬼,解题一定从这里入手！然后我们考虑把整的提出来，所以只考虑$mod$的话一定是以$d=gcd（n，m）$为循环节长度，然后就可以转换成一个简单的式子balabala。不过感觉考场上还是很难想到的QAQ

所以说作数论题，一定不要钻进死胡同。思路要开阔，充分挖掘题目的性质，找准突破点。也可以先打表找规律。

额。就是这样。