기본적인 수학 연산 접근 방법

1. 나머지 연산

• 문제에서 정답을 ~로 나눈 나머지를 출력해라 라는 말은 정답이 Int나 longlong과 같은 자료형의 범위를 넘어서기때문이다.
  • long : –9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807
  • int : –2,147,483,648 ~ 2,147,483,647
• (A+B)%C = (A%C+B%C)%C

2. 최대공약수(GCD)

• 유클리드 호제법
  • GCD(a,b)=GCD(b,r) r=a%b if r==0 then b is GCD
• 최소공배수(LCM)
  • GCD를 응용해서 구할 수 있음
    • AB=GCD(A,B)LCM

3. 소수

중요 에라토네스의 체를 기억하자

🙂 소수란? 약수가 1과 자기 자신밖에 없는 수
정의가 중요하다 . 다시말해서 N 이 소수가 되기위해서는 2보다 크거나 같고 N-1 작거나 같은 수로 나누어 떨어지면 안된다.

• 특정 N 이 주어질때 , 소수인지 아닌지 판별하는 방법

  1. 가장 생각하기 쉬운 소스

     ## n이 주어졌다고 생각해보면 
     
     if (n<2)  
     	return false;
     else
     {
     	for (int i=2;i<n-1;i++)
     	{
     		if (n%i==0)
     			return false;
     	}
     	return true		
     }

     시간복잡도 o(n)이 걸림

  2. i 를 n-1 까지 안 돌려도 됨

     // i는 n/2보다 작다. 여전히 시간복잡도 o(n)
     for (int i=2;i<n/2;i++)
     	{
     		if (n%i==0)
     			return false;
     	}
     
     // i는 루트 n 보다 작다.  이렇게 되면 시간복잡도 o(루트 n)
     for (int i=2;i*i<=n;i++)
     	{
     		if (n%i==0)
     			return false;
     	}

• N 까지 총 몇개의 소수가 있는지 구하는 방법

  방법 1 N이하의 숫자에 대해 모두 위의 방법을 적용시킨다.

  방법 2 에라토스테네스의 체

  	 1부터 N까지의 범위 안에 들어가는 모든 소수를 구해보자.

  1. 2부터 N 까지를 모두 써 놓는다.

  2. 제일 작은 수를 찾는다.

  3. 그 수의 배수를 모두 지운다.

  4. 반복한다.

     🤔 언제까지 반복해야될까?**

     더 이상 지워지는 것이 없을때까지? N까지 도달할때까지?

     제일 작은 수를 m이라고 할때 m의 제곱을 이 N보다 크거나 같아질 때까지 진행하면 됨

     단, m이 100만인 경우, m의 제곱은 1조가 되므로 int 자료값의 범위를 넘기기때문에 주의해야함.

5. 팩토리얼

1. 팩토리얼에서 0의 개수를 묻는 문제를 낸다면, 소인수분해를 해서 2*5 의 조합이 얼마나 있는지 봐야 한다. 당연히 2보다 5가 더 많이 나올 것이기때문에 5의 개수를 알면 0의 개수를 알아낼 수 있다

---

참고한 것 출처:

https://crazykim2.tistory.com/601

[차근차근 개발일기+일상]

백준 온라인 강의

이상 기본적인 수학 문제 관련해 어떤식으로 접근해야 빨리 효율적으로 구할 수 있는지 정리해보았습니다. 문제를 빨리 풀어봐야되는데 괜히 시간 낭비한 것 같기도 하네요 ㅠㅠ
문제가 있을시 삭제하겠습니다.
ㅎㅇㅌ