PS와 개발을 공부하자

문제 링크N <= 200000100만 이하의 N개의 수로 이루어진 배열 D가 주어진다.D의 모든 부분 집합 중 원소들의 gcd 가 1보다 큰 것들에 대해 그 집합의 원소 수 * gcd 를 모두 더한 값을 구하는 문제이다.cnt[i] : 입력으로 주어진 N개의 수들 중 i를 약수로 가지는 수들의 개수c[i] : 집합에 포함된 원소들의 gcd 가 i인 모든 부분 집합들의 원소의 수의 합이라고 정의내려보자.그럼 우리는 모든 i에 대해 c[i] 를 구할 수만 있다면, 1보다 큰 모든 i 에 대해 i * c[i] 를 계산하여 모두 더하면 답이 될 것이다.(왜냐면 원소들의 gcd 가 i 인 집합들에 대해 원소 수 * i 를 한다음 모두 더하면 결국 원소 소를 모두 더한뒤 i를 곱한 것과같기 때문이다.)그런데 c[i..

BOJ 9359번 : 서로소 1 <= A <= B <= 10^15 1 <= N <= 10^9 [A, B] 구간에 존재하는 수들 중 N와 서로소인 수들의 수를 구하는 문제이다. N을 소인수 분해 해보자. 2^a * 3^b * 5^c * 7^d * 11^e + ... 의 형태가 나올 것이다. [A, B] 구간의 수들중 N의 어떤 소인수의 배수도 아닌 수들은 N과 서로소일 것이다. 반대로 N의 어떤 소인수의 배수라면 N과 서로소가 아닐 것이다. 그럼 N과 서로소인 수를 세는 대신 N과 서로소가 아닌 수를 세서 [A, B] 구간에 있는 수의 수인 B - A + 1에서 뺴면 답을 구할 수가 있을 것이다. 그럼 [A, B] 에서 N과 서로소가 아닌 수는 어떻게 셀까? 위에서 말했듯이 N의 소인수들의 배수인 수들을 ..