7
6
2015
2

是时候补一波数论了

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

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

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

要敢于猜结论,学会类比。比如众所周知的有$$\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

 

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

额。就是这样。

Category: 涨姿势 | Tags: | Read Count: 1193
Avatar_small
sbit 说:
2015年7月12日 02:48

ai的值貌似是伯努利数吧?


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

| Theme: Aeros 2.0 by TheBuckmaker.com