Hi everyone, I'm trying to solve this problem however I get TLE. The problem asks for points such that gcd(x,y,z) = 1 inside of 0 <= x < L, 0 <= y < H, 0 <= z < W.

I'm using inclusion-exclusion with the mobius function to find the answer.

First I wrote a version going through all i from 1 to X: http://pastebin.com/UsShb6zF but I got TLE.

So I thought of optimizing it by going only through square free numbers, because in these numbers the value of the mobius function is different from zero, but I still get TLE.

Any idea about how to optimize it further?

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define MAXN 1000000

int mu[MAXN + 1],factor[MAXN + 1];
int sqfree[MAXN + 1],sz = 0;

long long visible(int X, int Y){
    long long ret = 0;
    
    for(int i = 0;i < sz && sqfree[i] <= X;++i){
        int cur = sqfree[i];
        ret += mu[cur] * (long long)(X / cur) * (Y / cur);
    }
    
    return ret;
}

long long visible(int X, int Y, int Z){
    long long ret = 0;
    
    for(int i = 0;i < sz && sqfree[i] <= X;++i){
        int cur = sqfree[i];
        ret += mu[cur] * (long long)(X / cur) * (Y / cur) * (Z / cur);
    }
    
    return ret;
}

int main(){
    memset(factor,-1,sizeof factor);
    mu[1] = 1;
    sqfree[sz++] = 1;
    
    for(int i = 2;i <= MAXN;++i){
        if(factor[i] == -1){
            mu[i] = -1;
            
            if(i <= MAXN / i)
                for(int j = i*i;j <= MAXN;j += i)
                    factor[j] = i;
        }else{
            int cont = 0,aux = i,p = factor[i];
            
            while(aux % p == 0 && cont < 2){
                aux /= p;
                ++cont;
            }
            
            if(cont == 2) mu[i] = 0;
            else mu[i] = -mu[i / p];
        }
        
        if(mu[i] != 0) sqfree[sz++] = i;
    }
    
    int X,Y,Z;
    
    while(scanf("%d %d %d",&X,&Y,&Z) == 3){
        --X; --Y; --Z;
        
        long long ans = visible(X,Y,Z) + visible(X,Y) + visible(Y,Z) + visible(Z,X);
        
        if(X >= 1) ++ans;
        if(Y >= 1) ++ans;
        if(Z >= 1) ++ans;
        
        printf("%lld\n",ans);
    }
    
    return 0;
}