题解 P1403 【[AHOI2005]约数研究】

川蜀霸王 · 2016-07-30 09:41:05 · 题解

线性筛

直接筛出f

#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
#include<cstdlib>
#include<algorithm>
const int N = 1e6 + 7;
int n, ans, prime[N], tot, f[N], g[N];
bool vis[N];
int main () {
    scanf ("%d", &n);
    ans = f[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!vis[i]) prime[++tot] = i, f[i] = 2, g[i] = 1;
        for (int j = 1; j <= tot && (long long) i * prime[j] <= n; ++j) {
            vis[i * prime[j]] = true;
            if (i % prime[j] == 0) {
//                if (i * prime[j] == 4) puts ("sdf");
                f[i * prime[j]] = f[g[i * prime[j]] = g[i]] + f[i];
                break;
            } else {
                f[i * prime[j]] = f[i] << 1;
                g[i * prime[j]] = i;
            }
        }
        ans += f[i];
    }
//    for (int i = 1; i <= 10; ++i) printf ("%d\n", f[i]);
    printf ("%d\n", ans);
    return 0;
}