백준(11690번) - LCM(1, 2, ..., n)(Java) (수학)

 계속 도전을 하다가 포기한 문제이다.

 

나의 풀이방식은

1. 1~n까지의 수에서 소수를 구해 소수는 그냥 곱해준다.

2. 그렇게 나온 결과와 나머지 값들 중 나눠 떨어지지 않는 수는 그 수의 제곱근을 곱해준다.

 

import java.util.*;
import java.io.*;

public class Main
{
	static int n;
	static long ans = 1;
	static long div = (long) Math.pow(2, 32);
	static boolean[] prime;
	
	public static void main (String[] args) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		
		era();
		
		for(int i = 2; i <= n; i++)
		{
			if (!prime[i]) ans = ((ans * i) % div);
			else 
			{
				if (ans % i > 0) ans = ((ans *(long)Math.sqrt(i)) % div);
			}
		}
		
		System.out.println(ans);
		
	}
	public static void era()
	{
		prime = new boolean[n+1];
		
		prime[0] = prime[1] = true;
		
		for(int i = 2 ; i*i <= n ; i++)
		{
			if(!prime[i])
			{
				for(int j = i*i ; j <= n ; j += i) prime[j] = true;
			}
		}
	}
}

실제로 테스트케이스 3까지는 무난하게 흘러갔으나, 숫자가 커지는 테스트케이스 4부터는 갑자기 쌓아오던 값이 0으로 초기화 돼버리는 문제가 발생했다.(뭐 정답이 일단 나와야 어디가 잘못인지 고치지...)

 

long으로는 담아내기 힘든가 싶어서 BigInteger도 사용했으나 똑같은 문제가 발생해 2시간가량 고민하고 chatGPT와 상의를 해봐도 얘도 모르는지 내 코드를 고쳐주지도 않고 고쳤다고 하길래 포기하고 넘겼다.

<문제>

https://www.acmicpc.net/problem/11690

 

<소스코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
    static int max = 100000001;
    static boolean[] is_prime = new boolean[max];
    static List<Integer> plist = new ArrayList<>();
    static long mod = (long) 1 << 32;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        sieve(n);

        long res = 1;
        plist.add(2);
        for (int i = 3; i <= n; i += 2) {
            if (is_prime[i]) {
                plist.add(i);
            }
        }

        for (int prime : plist) {
            long power = prime;
            while (power * prime <= n) {
                power *= prime;
            }
            res = (res * power) % mod;
        }

        System.out.println(res);
    }

    public static void sieve(int n) {
        for (int i = 2; i <= n; i++) {
            is_prime[i] = true;
        }
        for (int i = 2; i * i <= n; i++) {
            if (!is_prime[i]) {
                continue;
            }
            for (int j = i * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }
}