수학2 연속한 수의 XOR sum ll xorSum(ll n) { int m = n % 4; if (m == 0) return n; if (m == 1) return 1; if (m == 2) return n + 1; return 0; } 1부터 n까지의 수의 XOR sum은 위와 같다. 자세한 내용은 여기에서 볼 수 있다. ll xorSum(ll l, ll r) { return xorSum(l - 1) ^ xorSum(r); } 구간 [L : R] 의 xor 합 역시 같은 두 수를 xor 하면 0이 된다는 사실을 이용하여 구할 수 있다. 2020. 12. 25. 치킨 쿠폰 문제: 처음에 교환 쿠폰 n장이 있고, k장을 사용하면 1장의 쿠폰을 줄 때, 최대 몇 마리의 치킨을 받을 수 있는가? 사용한 총 쿠폰 수를 t라고 하자. 처음 n장이 있으니 t의 초기값은 n이다. 새로 받을 수 있는 쿠폰은 n // k 장이다. t += n // k * 가지고 있는 쿠폰으로 최대한 많이 교환 이때 남는 쿠폰은 n // k + n % k 장이다. n = n % k + n // k * 교환하지 못한 n % k 장 + 이제 새로 받은 n // k 장 이것을 새로 받을 수 있는 쿠폰이 0장이 될 때까지 반복하면 된다. t = n while n//k > 0: t += n//k n = n//k + n%k 이제 t를 한번에 구하자. k개의 쿠폰을 사용하면 1개의 쿠폰을 받으므로, k - 1개의 쿠폰.. 2020. 11. 25. 이전 1 다음
