BZOJ2693: jzptab(莫比乌斯反演)

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 2068  Solved: 834
[Submit][Status][Discuss]

Description

 

Input

一个正整数T表示数据组数

接下来T行 每行两个正整数 表示N、M

Output

T行 每行一个整数 表示第i组数据的结果

Sample Input

1

4 5

Sample Output

122

HINT
T <= 10000

N, M<=10000000

HINT

 

Source

版权所有者： 倪泽堃

Orz gxz

这题好神仙啊，就是把这个换成了多组询问

我们可以继续利用上一个题的公式推

$f(n)$是两个积性函数的乘积，同样也是积性函数

考虑只有一个素因子时$f(n) = n * (1 - n)$

当$n$不为质数时$n = i * p$，此时$n$一定包含$p^2$这个因子，所以$f(n) = p * f(i)$

#include<cstdio>

#include<algorithm>

#define LL long long

using namespace std;

const int MAXN = 1e7 + , mod = ;

int T, N, M;

int tot, vis[MAXN];

LL f[MAXN], prime[MAXN];

void GetF(int N) {

    f[] = ;

    for(int i = ; i <= N; i++) {

        if(!vis[i]) prime[++tot] = i, f[i] = (i - 1ll * i * i  % mod + mod) % mod;

        for(int j = ; j <= tot && i * prime[j] <= N; j++) {

            vis[i * prime[j]] = ;

            if(!(i % prime[j])) {

                f[i * prime[j]] = f[i] * prime[j] % mod;

                break;

            } else f[i * prime[j]] = f[i] * f[prime[j]] % mod;

        }

    }

    for(int i = ; i <= N; i++) f[i] = (f[i - ] + f[i] + mod) % mod;

}

LL S(LL x) {

    return (x * (x + )) /  % mod;

}

int main() {

    scanf("%d", &T);

    GetF(1e7 + );

    while(T--) {

        int N, M, last;

        LL ans = ;

        scanf("%d %d", &N, &M);

        if(N > M) swap(N, M);

        for(int i = ; i <= N; i = last + ) {

            last = min(N / (N / i), M / (M / i));

            ans = (ans + S(N / i) * S(M / i) % mod * (f[last] - f[i - ] + mod) % mod) % mod;

        }

        printf("%lld\n", ans);

    }

    return ;

}

/*

2

4 5

123456 654321

*/