수학10 cf 596 div2 D - Power products (소인수분해, 수학) https://codeforces.com/contest/1247/problem/D 최대 1e5의 크기가 n인 배열 a가 주어진다. 임의의 자연수 x에 대해 ai * aj = x^k를 만족하는 쌍의 개수를 구하라. 0~i-1번 중 i번과 쌍을 이루는~ ai를 소인수분해해서 (j번째로 작은 소수가 나온 횟수 % k)값을 적절히 벡터(v)에 담으면, 0~i-1번의 벡터 중 v와 쌍을 이루는 벡터의 모양은 하나로 정해진다. map로 그값을 유지하여 계산해 나간다. 1e5이하 소수는 10000개정도 되니까 위 방법을 그대로 적용하려면 시공간복잡도가 너무 크다. 제곱근1e5 이하의 소수를 smallprimes라 하고 그 외 소수를 bigprime이라고 하자. a는 최대 1e5이므로 제곱근1e5보다 큰 소수(bigp.. 2020. 3. 15. cf 626 div2 D - present (수론, 이분탐색) https://codeforces.com/contest/1323/problem/D 어렵지만 여기저기서 출제된 적이 있는 문제. 핵심 아이디어는 가져가자 최대 4e5개의 원소 n개를 갖는 배열이 있다. 원소는 1e7이하의 자연수를 갖는다. n개 중 2개 원소의 가능한 모든 쌍에 대해 합을 구해 모두 xor한 값을 구해라 (a1+a2)⊕(a1+a3)⊕ … ⊕(a1+an)⊕(a2+a3)⊕ … ⊕(a2+an)…⊕(an−1+an) 한 쌍의 합의 최댓값은 2e7이므로 답을 ans라 했을때 ans는 24개 비트로 표현 가능하다. ans의 k번째 비트가 켜져있는지 nlogn에 알 수 있다. a의 원소들은 k+1번 이후의 비트는 k번째 비트에 영향을 주지 않는다. b 2020. 3. 15. log2(n)값 구하기 k = log2(n)이라고 할때 floor(k)값을 구하는 로직 int k = 1; for (k = 1; (1 2020. 1. 8. codeforces #612 div2 D - Numbers on Tree (그래프, 수학, 구현) https://codeforces.com/contest/1287/problem/D 실패할 조건을 찾은데서 그친 문제. 시험볼 당시엔 좀만 보면 풀 수 있을 것 같다고 생각했지만, 꽤 오래 생각해봐도 못풀었다. 최대크기 2000의 트리가 주어진다. 각 정점마다 a[i]값을 갖는다. (이 값은 주어지지 않는다. 찾아내야 함) 이 때, 각 정점이 루트가되는 서브트리에서 현재 정점의 a값보다 작은 a값을 갖는 정점들의 수를 c값이 주어질때 가능한 a배열을 구해라. 위->아래, 왼쪽->오른쪽 순서대로 각 정점 번호가 1,2,3,4,5이다. (오른쪽 리프노드가 5번정점이다.) 크게 쓰인 수가 a값이고 괄호 안의 값이 c값이다. 1. 실패조건 각 정점을 루트로 하는 서브트리의 크기를 sz[i]라고 하자. 그러면 c[.. 2020. 1. 7. 이전 1 2 3 다음
