소인수분해4 cf #538 div2 C - Trailing Loves (소인수분해, 수학) https://codeforces.com/contest/1114/problem/C n! 에 어떤 소수가 몇개 들어있는지 로그시간에 파악하는 법 확인. 오버플로우를 피하기 위한 조건문 확인. 최대 1e18의 n과 최대 1e12의 b가 주어진다. n!을 b진법으로 표현했을 때 trailing zero의 수를 세라. (ex. 9800은 10진법으로 trailing zero가 두개 있다.) n!을 b로 몇번 나눌 수 있는지 구하면 된다. b를 소인수분해하여 p ^ x꼴의 인수들에 대해서, n!에 그 하나하나의 인수가 나오는 횟수들의 최소를 구하면 된다. n!에 어떤 소수 x가 몇 개 들어있는지 반환하는 함수 f를 이용해서 풀 수 있다. ll f(ll x) { ll ret = 0; ll t = x; x = 1; .. 2020. 4. 2. 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. Educational #56 D - GCD counting (트리(숲) 지름, 소인수분해) https://codeforces.com/contest/1101/problem/D 소인수분해 시간복잡도를 잘못 파악하고 있었다. 루트n인줄 알았는데 소인수분해는 loglogn이다. (에라토스가 루트n이다) 트리 지름 구하는 방법은 알고 있었지만 숲에서 최대 지름을 구하는 것을 O(n)에 할 방법을 생각하지 못했다. 같은 시간복잡도를 갖는 코드라도 시간제한이 빡빡해서 최적화를 해줘야 한다. (난이도에 비해 푼 사람이 적은 이유인듯) 단일 트리와 다른 특별한 알고리즘을 사용하진 않는다. 한 점 잡고 제일 먼 점 u와 u에서 제일 먼 점 v와의 거리를 모든 트리에 대해 구하면 된다. 하나의 트리에 대해 최대 지름을 구한 후, 방문처리를 위한 vst배열을 초기화하지 않고 다음 트리에 대해 최대 지름을 구하는 부.. 2020. 3. 13. 소인수 분해, 약수의 개수, 오일러 피함수 에라토스테네스 :https://suuntree.tistory.com/36?category=805933 소인수분해 자체로는 문제가 많이 나오지않지만 오일러 피함수는 알고있어야 한다. 1. 소인수분해 : O(loglogn) -> while문 수행횟수 log, while문에서 n의 범위를 줄여줌 n이 소수가 아니라면, n은 루트n 이하의 소인수를 갖는다. i==2부터 차례대로 n을 나눌 수 있다면 i로 n을 더이상 나눌 수 없을 때까지 나누면서 진행한다. 과정이 끝나면 n=1 또는 n=소수가 된다. ll n; cin >> n; vector p; for (ll i = 2; i * i 2020. 1. 30. 이전 1 다음
