수론6 Educational 84 div2 D - Infinite Path (약수, 수론, 후속노드그래프) https://codeforces.com/contest/1327/problem/D 약수를 모두 구하는 건 O(루트n), 전처리 후 O(n^(1/3)) 소인수분해는 필요 없다. 사이클 덩어리들이 주어진다. 사이클에 포함된 u,v에 대해 u->v면 v->u경로가 반드시 있다.(주어진 p 배열이 순열이므로) 번호마다 색이 주어진다. 사이클에서 k번째 후속노드를 가리키는 그래프가 모두 같은 색을 이룰 때 infinite path를 이룬다고 하자. infinite path가 존재하기 위한 k의 최소값을 구해라. 사이클의 크기의 1이아닌 약수 k번째 후속노드를 가리키는 그래프는 쪼개진다. 그 외의 경우 사이클의 순서는 바뀔 수 있지만 구성요소는 바뀌지 않는다. 사이클마다 약수번째 후속노드를 가리키는 그래프가 inf.. 2020. 3. 24. 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. 조합의 소수 모듈러 값 빠르게 구하기 (n C m % p) https://ryulstory.tistory.com/62 페르마 소정리에 따르면 p가 소수인 경우 a^(p-1) = 1 (mod p) 1/a mod p == a^(p-2) 즉 다음을 만족함 (a*b) % p = (a%p) * (b%p) (a/b) % p = (a%p) * (b^(p-2) % p) nCk (mod p) = n! /(k! * (n-k)!) (mod p) = (n! mod p) * ((k! * (n-k)!)^(p-2) mod p ) 다음 두 배열을 전처리해준다. O(n) fac[x] : x! % MOD fac_inv[x] : (x!)^(-1) %MOD -> n * inverse(n!) = inverse((n-1)!) 를 이욯 O(1)에 nCm % p 를 구할 수 있다. const ll MOD.. 2020. 3. 10. 이전 1 2 다음