contest11

contest

contest11

1. 各种公式

平方和公式 $1^2+2^2+3^2+\cdots+n^2={n(n+1)(2n+1)\over{6}}$

推导过程 important!

$(n+1)^3-n^3=3n^2+3n+1$
$n^3-(n-1)^3=3(n-1)^2+3(n-1)+1$
$\cdots$
$2^3-1^3=3*1^2+3*1+1$
相加得：$(n+1)^3-1^3=3*{\sum_{i=1}^n i^2}+3*{\sum_{i=1}^n i}+n$
即$\sum_{i=1}^n i^2={n(n+1)(2n+1)\over{6}}$

立方和公式$1^3+2^3+3^3+\cdots+n^3={{n^2(n+1)^2}\over{4}}$

四次方和公式$1^4+2^4+3^4+\cdots+n^4={n(n+1)(2n+1)(3n^2+3n-1)\over{30}}$

这样可以推出k次方和公式，不再赘述。

2. 求$\lfloor\frac{n}{1}\rfloor+\lfloor\frac{n}{2}\rfloor+\cdots+\lfloor\frac{n}{n}\rfloor$

for (int i=1;i<=n;i++)
    sum+=n/i;

O(n),不够快

1. 可以求出连续区间：$\frac{n}{i}$=$\frac{n}{j}$

此时$j={n\over{n\over{i}}}$(/为整除）

//O（sqrt(n))   方法1
for (int i=1;i<=n;i=j+1)
{
    int j=n/(n/i);
    sum+=(j-i)*calc(i);//calc(i)计算n/i
}

2. 也可以先暴力求$1$~$sqrt(n)$,剩余部分：

//O(sqrt(n)) 方法2
int m=sqrt(n);
for (int i=1;i<=m;i++)
    sum+=n/i;
for (int i=n/m;i>1;i--)
{
    //从n/i+1到n/(i-1)
    int a=n/i,b=n/(i-1);
}