【51nod】1244 莫比乌斯函数之和

题解

求积性函数的前缀和？杜教筛！

这不给一发杜教筛入门必备之博客= =

https://blog.csdn.net/skywalkert/article/details/50500009

好了，然后我试着在这里推导一下式子

我们利用一个卷积就是

$\mu * I = e$

写成熟悉的形式就是

$[n = 1] = \sum_{d | n} \mu(d)$

哎？和杜教筛有什么关系啊

$1 = \sum_{i = 1}^{n}[i = 1] = \sum_{i = 1}^{n} \sum_{d | i}\mu(d) = \sum_{i = 1}^{n} \sum_{d = 1}^{\lfloor \frac{n}{i} \rfloor} \mu(d) = \sum_{i = 1}^{n} M(\lfloor \frac{n}{i} \rfloor) M(n) = 1 - \sum_{i = 2}^{n} M(\lfloor \frac{n}{i} \rfloor)$
这样的话，我们就可以只用$\sqrt{n}$个值算出$M(n)$了

用一个hash记忆化搜索一下就好了= v =

代码

#include <bits/stdc++.h>

#define MAXN 10000005

//#define ivorysi

#define enter putchar('\n')

#define space putchar(' ')

#define fi first

#define se second

#define pb push_back

#define mp make_pair

#define eps 1e-8

#define mo 974711

#define pii pair<int,int>

using namespace std;

typedef long long int64;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;char c = getchar();T f = 1;

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 + c - '0';

	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {putchar('-');x = -x;}

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

struct node {

    int64 x,v;

    int next;

}E[1000005];

int head[mo + 5],sumE;

int64 a,b;

int prime[5000005],tot,M[MAXN],mu[MAXN];

bool nonprime[MAXN];

void add(int u,int64 x,int64 v) {

    E[++sumE].x = x;E[sumE].v = v;E[sumE].next = head[u];

    head[u] = sumE;

}

void Insert(int64 x,int64 v) {

    add(x % mo,x,v);

}

int64 Query(int64 x) {

    int u = x % mo;

    for(int i = head[u] ; i ; i = E[i].next) {

	if(E[i].x == x) return E[i].v;

    }

    return 1e18;

}

int64 f(int64 x) {

    if(x <= 10000000) return M[x];

    int64 c = Query(x);

    if(c != 1e18) return c;

    int64 res = 0;

    for(int64 i = 2 ; i <= x ; ++i) {

	int64 r = x / (x / i);

	res += (r - i + 1) * f(x / i);

	i = r;

    }

    res = 1 - res;

    Insert(x,res);

    return res;

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    mu[1] = 1;M[1] = 1;

    for(int i = 2 ; i <= 10000000 ; ++i) {

	if(!nonprime[i]) {

	    mu[i] = -1;

	    prime[++tot] = i;

	}

	for(int j = 1 ; j <= tot ; ++j) {

	    if(prime[j] > 10000000 / i) break;

	    nonprime[prime[j] * i] = 1;

	    if(i % prime[j] == 0) mu[i * prime[j]] = 0;

	    else mu[i * prime[j]] = -mu[i];

	}

	M[i] = M[i - 1] + mu[i];

    }

    read(a);read(b);

    out(f(b) - f(a - 1));enter;

    return 0;

}

巴特西

【51nod】1244 莫比乌斯函数之和

题解

代码

最新文章

热门文章