Luogu

分析

容易发现,要求的是 $f(n)=\sum\limits_{i=2}^nf(\lfloor\frac{n}{i}\rfloor)$。

显然可以数论分块,拿 $\mathrm{unordered\_map}$ 记搜,再吸口氧就能过了

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

unordered_map<int,ll> S;

inline ll calc(int n) {
    if (n==1) return 1;
    if (S.find(n)!=S.end()) return S[n];
    ll res=0;
    for (re int l=2,r;l<=n;l=r+1) {
        r=n/(n/l);
        res+=calc(n/l)*(r-l+1);
    }
    return S[n]=res;
}

int main() {
    printf("%lld\n",calc(read()));
    return 0;
}
最后修改:2019 年 09 月 26 日 01 : 14 PM