Educational Codeforces Round 001. A, B, C, D
A. Tricky Sum 문제 https://codeforces.com/contest/598/problem/A 문제요약 N값이 주어지면 2의 0, 1, ... , inf 제곱들에 대해 음수로 더하고 그 이외 수에 대해 양수로 더한 합을 출력해야한다. 풀이 1+2+...+2^(n-1) = 2^n - 1임을 알고 있을 때 전체에서 2의 제곱수들에 대해 두번 빼주면 된다. 즉, 수식으로 나타내면 다음과 같다. N(N+1)/2 - 2(2^[log_2{N}] -1) 소스코드 #include typedef long long ll; int main(){ int T; scanf("%d",&T); while(T--){ ll n, p=1; scanf("%lld",&n); for(int t=n; t; t>>=1, p1)-(..
[백준] GCD 곱
문제 : https://www.acmicpc.net/problem/14860 문제요약 : GCD(1, 1) × GCD(1, 2) × ... × GCD(1, M) × GCD(2, 1) × GCD(2, 2) × ... × GCD(2, M) × ... × GCD(N, 1) × GCD(N, 2) × ... × GCD(N, M)을 구해라 조건 : 1. 1 ≤ N, M ≤ 15,000,000 해설 : i) Naive Solution 각각의 i(1 ≤ i ≤ N), j(1 ≤ j ≤ M)에 대해 GCD(i, j)를 구해 곱하면서 O(NM)으로 구할 수 있겠죠? -> 15000000^2이므로 너무 느립니다 ii) 조금더 빠르게 N=8, M=8이라 합시다. GCD(i,j)들 중에 2의 인수가 얼마 있는지 알아봅시다. 1..