ZOJ3435

题意略。

思路：

将每一个点的坐标 (x,y,z) 与 (1,1,1) 相减，得到向量 (x - 1,y - 1,z - 1) 我们实际上就是要求出这样互质的三元组有多少对就行了。

我们把这个长方体分成3部分：

1.三条坐标棱 2.在坐标棱上的三个表面（除去坐标棱） 3.长宽高分别为[L - 1,W - 1,H - 1]的长方体

三条坐标棱我们只要开3枪，就可以贯穿这个部分，ans += 3。

至于2和3，我们可以用莫比乌斯的第二类反演来解决。

在用莫比乌斯反演时，如果我们一一枚举因子，就会T，我们来考虑一个sqrt(n)的优化。

比如说19这个数：

19 / 1 = 19，19 / 2 = 9，19 / 3 = 6，19 / 4 = 4，19 / 5 = 3，19 / 6 = 3，19 / 7 = 2，19 / 8 = 2，19 / 9 = 2，19 /10 = 1，......，19 / 19 = 1

在进行反演时，我们必然是通过枚举分母，计算出F(i) = (L / i) * (W / i) * (H / i)。

然而可以发现，7，8，9只要枚举一个就行，10~19也只需要枚举一个就行，如果我们用sum[ i ] 来维护mu[ i ]的前缀和，

那么ans += mu[ 7 ] * 19 / 7 + mu[ 8 ] * 19 / 8 + mu[ 9 ] * 19 / 9 等价于 ans += (sum[ 9 ] - sum[ 6 ]) * 19 / 7。

我们知道对于任意一个数x >= a * b，它的这种小于它且可以产生不同b的a最多有2 * sqrt(x)个。

详见代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const LL maxn = ;

LL l,w,h;

bool check[maxn];

LL prime[maxn];

LL mu[maxn],sum[maxn];

void mobius(){

    memset(check,false,sizeof(check));

    mu[] = ;

    sum[] = ;

    int tot = ;

    for(LL i = ;i < maxn;++i){

        if(!check[i]){

            prime[tot++] = i;

            mu[i] = -;

        }

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

            if(i * prime[j] > maxn) break;

            check[i * prime[j]] = true;

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

                mu[i * prime[j]] = ;

                break;

            }

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

        }

        sum[i] = sum[i - ] + mu[i];

    }

}

int main(){

    mobius();

    while(scanf("%lld%lld%lld",&l,&w,&h) == ){

        LL ans = ;

        LL len = min(l,min(w,h)),last;

        for(LL i = ;i < len;i = last + ){

            LL a = (l - ) / i,b = (w - ) / i,c = (h - ) / i;

            last = min((l - ) / a,min((w - ) / b,(h - ) / c));

            ans += (sum[last] - sum[i - ]) * (a * b * c);

        }

        len = min(l,h);

        for(LL i = ;i < len;i = last + ){

            LL a = (l - ) / i,b = (h - ) / i;

            last = min((l - ) / a,(h - ) / b);

            ans += (sum[last] - sum[i - ]) * (a * b);

        }

        len = min(l,w);

        for(LL i = ;i < len;i = last + ){

            LL a = (l - ) / i,b = (w - ) / i;

            last = min((l - ) / a,(w - ) / b);

            ans += (sum[last] - sum[i - ]) * (a * b);

        }

        len = min(w,h);

        for(LL i = ;i < len;i = last + ){

            LL a = (w - ) / i,b = (h - ) / i;

            last = min((w - ) / a,(h - ) / b);

            ans += (sum[last] - sum[i - ]) * (a * b);

        }

        ans = ans + ;

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

    }

    return ;

}

巴特西

ZOJ3435

最新文章

热门文章