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;
}
I finally solve it, the key fact is that the values of
(X / cur) , (Y / cur) , (Z / cur)
don't change many times.
A similar but more interesting version: http://www.spoj.com/problems/ADVNTURE/