A simple Blog for wyx I've been down the bottle hoping.
BZOJ 2820 莫比乌斯反演
发表于: | 分类: Oi | 评论:0 | 阅读:183

题目大意
$$ans=\sum\limits_{i=1}^n \sum\limits_{j=1}^m{[\gcd(i,j)==prime]}$$

首先容易知道这个$prime$ 显然是在 $\min({m,n})$之内的
所以得到
$$ans=\sum\limits_{p=1}^{\min{(m,n)}}{isprime[p] \sum\limits_{i=1}^n\sum\limits_{j=1}^m{[\gcd(i,j)==p]}}$$

然后反演一下后面的那个东西得到
$$ans=\sum\limits_{p=1}^{\min{(m,n)}}{\sum\limits_{p|d}{F(d)\mu(\frac{d}{p})}},F(d)=\sum\limits_{i=1}^n\sum\limits_{j=1}^m{[d|\gcd(i,j)]}$$
然后换一下两个$\sum$的位置,得到
$$ans=\sum\limits_{d=1}^{\min(m,n)}\lfloor\frac{m}{p}\rfloor\lfloor\frac{n}{p}\rfloor\sum\limits_{p|d}isprime[d]
mu(\frac{d}{p})$$
后面那个随便筛筛求个前缀和就行了
前面那个是$\sqrt{n}$跑一下就行了
复杂度是$O(n)+T\sqrt{n}$的
得开$long \quad long$

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 1e7;
typedef long long LL;
using namespace std;

LL mu[N+5],F[N+5],g[N+5],prime[N],cnt;

void init(){
    mu[1] = 1;
    register int i,j;
    for(i=2;i<=N;++i){
        if(!F[i]){
            prime[++cnt] = i;
            mu[i] = -1;
        }
        for(j=1;prime[j]*i<=N;++j){
            F[prime[j]*i] = 1;
            if(i%prime[j] == 0) break;
            mu[i*prime[j]] = -mu[i];
        }
    }
    for(i=1;i<=cnt;++i)
        for(j=1;prime[i]*j<=N;++j)
            g[prime[i]*j] += mu[j];
    for(i=1;i<=N;++i)
        g[i] += g[i-1];
}

inline LL calc(LL x,LL y){
    int last = 1;
    LL ans = 0;
    register int i;
    for(i=1;i<=x&&i<=y;i=last+1){
        last = min(x/(x/i),y/(y/i));
        ans += (x/i)*(y/i)*(g[last]-g[i-1]);
    }
    return ans;
}

inline int read(){
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int main(){
    init();
    int T = read();
    for(int i=1;i<=T;++i){
        int x = read(), y = read();
        printf("%lld\n",calc(x,y));
    }
}
Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP