[BOJ 7938] Mniam mniam

'냠냠' 이라는 문제이다! 냠냠

$n\times m$ 격자에서 원점으로부터 각 점들로 직선을 긋는데 서로 다른 직선의 개수를 구하는 문제로 바꿔 볼 수 있다.  그럼 겹치는 직선이 뭔지만 알면 문제를 풀 수 있겠다. 기울기가 $b/a$이고 기약분수라고 한다면 $2b/2a,\ 3b/3a...$등 이 겹치는 직선이므로 1개만 세야한다. 이때 관찰할 수 있는 사실은 $b/a$가 기약분수가 아니면 반드시 겹치는 직선이 된다는 사실이다. 그럼 $b/a$가 기약분수가 되는 $a,b$쌍의 개수를 세면 된다. 이것은 다음과 같이 나타난다.

\[\sum_{i=1}^{n} \sum_{j=1}^{m} [\gcd(i,j)=1]\]

이때 Mobius inversion을 적용하면

\[\sum_{d=1}^{\min(n,m)} \mu(d)\lfloor n/d \rfloor \lfloor m/d \rfloor \]

아직 고려하지 않은 것은 기울기가 0인 직선과 무한대인 직선이다. $n,m=0$이면 이런 직선은 없을 것이고 $n+m>0,\ nm=0$인 경우 저런 직선은 1개 있다. 이외의 경우 2개가 있다. 따라서 전부 더해주면 된다.

 

아래는 정답 코드가 있다!

# 코드 보기

#include<stdio.h>
#define M 1000000
typedef long long ll;
ll mu[M+1];
int sp[M+1];
int min(int a,int b){
    return a>b?b:a;
}
int main(){
    ll i,j;
    for(i=1;i<=M;i++) mu[i]=1;
    for(i=2;i<=M;i+=2){
        if(sp[i]) continue;
        for(j=i;j<=M;j+=i){
            sp[j]=1;
            if(j%(i*i)==0) mu[j]=0;
            else{
                mu[j]*=-1;
            }
        }
        if(i==2) i=1;
    }
    for(i=2;i<=M;i++){
        mu[i]+=mu[i-1];
    }
    int T,n,m;
    scanf("%d",&T);
    while(T--){
        ll ans=0,mi;
        scanf("%d %d",&n,&m);
        mi=min(n,m);
        for(i=1;i<=mi;i=j+1){
            j=min(n/(n/i),m/(m/i));
            ans+=(n/i)*(m/i)*(mu[j]-mu[i-1]);
        }
        if(n*m==0 && n+m) ans+=1;
        if(n*m) ans+=2;
        printf("%lld\n",ans);
    }
}

# 닫기