BOJ 1016 제곱 ㄴㄴ 수

 

문제 링크 : https://www.acmicpc.net/problem/1016

1016번: 제곱 ㄴㄴ 수

 

입력값의 컸기 때문에 걱정이 앞서서 한참 고민했던 문제이다.

그런데 결론은 효과적인 알고리즘이 필요없다는 것이었다.

 

절차

입력의 작은 수를 m , 큰 수를 M 이라고 하자. 

no 배열은 해당 수가 제곱수를 약수로 가지면 1 이고 아니면 0 이다. (우리는 0 의 개수를 세야 한다.)

no[0] 은 m 이 제곱수를 가지는지 여부를 저장하고 no[M-m] 은 M 이 어떤지를 저장한다.

(입력이 큰 수 이므로 m 을 뺀 위치에 ㄴㄴ 수인지 여부를 저장한다는 뜻이다.)

 

그리고 $2^2=4$ 부터 시작해서 $3^2, 4^2 , \cdots, $ 의 배수들을 차례로 조사해서,

m 과 M 사이에 있으면 그 위치에 1을 기록한다.

 

m 을 $i^2$으로 나눈 몫을 q 라 하면 두 가지 가능성이 있다.

1. $m=(i^2)*q$ 이면 시작 위치는 m 이고 no[0] 부터 기록된다.

2. 그렇지 않으면 m, M 사이의 최초의 $i^2$ 의 배수는 $(q+1)*(i^2)$ 이다.

 

코드부터 보고 시간 복잡도 분석은 아래에서 한다.

 

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int no[1000001];

int main(){
    ll m,M; scanf("%lld%lld",&m,&M);
    for(ll i=2;i*i<=M;i++){
        ll square=i*i;
        ll q=m/square;
        ll p=0;
        if(q*square!=m) p=(q+1)*square-m;
        for(;m+p<=M;p+=square)
            no[(int)p]=1;
    }
    
    int ans=0;
    for(int i=0;i<=(int)(M-m);i++)
        ans+=(no[i]==0);
    printf("%d\n", ans);
}

 

처음 걱정했던 것은 위 코드에서 for 루프가 두 개 중첩되기 때문이었다.

입력 조건의 M 의 크기로 인해 i 는 최대 $10^6$ 이고 안쪽 루프가 복잡하면 시간 초과가 우려되었던 것이다.

 

그런데 생각해보니 큰 문제가 없었다.

제곱의 배수들을 조사하고 있는 중이므로,

안쪽 루프에서 수행되는 명령의 총 개수는 다음에 근사할 것이다.

$$ \frac{M-m}{2^2} +\frac{M-m}{3^2} + \cdots \frac{M-m}{i^2} +\cdots $$

잘 알려져 있는 것처럼 제곱의 역수의 합은 수렴하며 상계로 2를 가진다.

$$1+ \frac1{2^2}+\frac1{3^2}+\frac1{4^2}+\cdots+\frac1{n^2}+\cdots \le 2 $$

 

결국 이 방식은 시간 복잡도가 $O(M-m)$ 으로 동작함을 알 수 있다.