标签： 数学

发布于

[暑期集训][数学][数论][组合数学] SPOJ Square-free integers

（其实一开始想的是错的，实际上就是mu[i]^2的前缀和S

先考虑对立面，2到n之间有多少个数可以被平方数整除？可以枚举从2到sqrt(n)，然后把可以被这些数字的平方整除的算上，也就是n/(i^2)个对于每个来说。但是这里会有重复的，比如i分别为2，3，6时，算上了4，9，36，其中36被算了两遍，所以要加加减减。（好吧其实我也还没自己证明出来但是今天有点疲回头填坑ooorz
继续阅读“[暑期集训][数学][数论][组合数学] SPOJ Square-free integers”

发布于

[暑期集训][数学][递推] 51nod 1383

题意要求求出给定整数分解为2的幂之和的方法数量。（貌似这题还有两个加强版orz日后填坑

写出前几项后可以观察出来规律：当n为奇数的时候 f(n)=f(n-1)，当n为偶数的时候f(n)=f(n/2)+f(n-2)。

这个规律的由来其实很简单，奇数的时候一定每一种分解都有至少一个1，说明这个1不是造成这些分法不同的原因，那么去掉他之后这些分法仍然是不同的，也就是数量没有减少，所以f(n)=f(n-1)。        而偶数的时候可以观察到分法可以分为两类，一类是有1的，这时候必定至少有两个1（因为n为偶数），换句话说这一类里面每种分法都有两个1，那么跟奇数那个同理这个也不是造成这些分法彼此不同的原因，所以去掉之后仍然是不同的也就是数量不会减少，这一部分相当于是f(n-2)；   另一部分都是2的倍数，那么把他们全部除以2的话也仍然保持不同也就是数量没有变，也就是说这一部分相当于f(n/2)。

一开始没写记忆化果断T了几发。。。
继续阅读“[暑期集训][数学][递推] 51nod 1383”