프로그래밍

https://www.acmicpc.net/problem/2004

[난이도] Silver2
[유형] 수학

[풀이]
nCm 은 n!/(m!x(n-m)!) 로 표현된다.

문제 https://www.acmicpc.net/problem/1676 에서 봤듯이 끝의 0의 개수는 어떤 수를 소인수분해 했을 때 5x2가 몇개나 있는지에 따라 결정된다.
n!/(m!x(n-m)!) 식에서 2와 5가 최종적으로 몇개 남는지를 구하고 둘중 최솟값을 출력하면 된다.

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.min
fun get(p:Int,k:Int):Int{
    var cnt=0
    var n=p
    while(n>0){
        n/=k
        cnt+=n
    }
    return cnt
}
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val ip=readLine().split(' ')
    val N=ip[0].toInt()
    val M=ip[1].toInt()
    val a = get(N,2)-get(N-M,2)-get(M,2)
    val b = get(N,5)-get(N-M,5)-get(M,5)
    println(min(a,b))
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver2/2004.cpp

https://www.acmicpc.net/problem/1676

[난이도] Silver3
[유형] 수학

[풀이]
모든 10은 2x5로 만들어지기 때문에 1~N 모든 수를 소인수 분해 했을 때 2와 5의 개수 중의 최솟값이 답이다.
항상 5가 더 적은 것이 보장되기 때문에 5의 개수만 구하면 된다.

import java.io.BufferedReader
import java.io.InputStreamReader
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val N=readLine().toInt()
    var cnt:Int=0
    for(i in 1..N) {
        var j=i
        while(j>0 && j%5==0){
            cnt++
            j/=5
        }
    }
    println(cnt)
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver3/1676.cpp

https://www.acmicpc.net/problem/6588

[난이도] Silver1
[유형] 수학

[풀이]
에라토스테네스의 체를 이용해 소수를 미리 구해준다

import java.io.BufferedReader
import java.io.InputStreamReader
import java.lang.IndexOutOfBoundsException
import java.util.*
const val mxN = 1000000
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){

    var list = ArrayList<Int>()
    var nP = BooleanArray(mxN+1)
    nP[1]=true

    for(i in 2..mxN/2){
        if(nP[i]) continue
        var j=i*2
        while(j<=mxN){
            nP[j]=true
            j+=i
        }
    }
    for(i in 2..mxN) {
        if(!nP[i]) list.add(i)
    }
    while(true){
        var ip = readLine().toInt()
        if(ip==0) break

        for(a in list){
            if(!nP[ip-a]){
                println("$ip = $a + ${ip-a}")
                break;
            }
        }
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver1/6588.cpp

https://www.acmicpc.net/problem/1929

[난이도] Silver2
[유형] 에라토스테네스의 체

[풀이]

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var ip = readLine().split(' ')
    var n=ip[0].toInt()
    var m=ip[1].toInt()
    var notPrime = BooleanArray(1000001)
    notPrime[1]=true
    for(i in 2..m){
        if (notPrime[i]) continue
        var j = i*2
        while(j<=m){
            notPrime[j]=true
            j+=i
        }
    }
    for(i in n..m) if(!notPrime[i]) println(i)
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver2/1929.cpp

https://codeforces.com/contest/1485/problem/A

[난이도] Div.2
[유형] 수학

[풀이]
아이디어 : +와 / 연산을 사용할 때 +연산을 먼저 하는게 무조건 이득이다.

1. b,b+1,b+2,b+3...b+i 를 검사 (+를 몇개 쓸건지..)
2. '/'가 영향력이 더 크기때문에 +를 많이 써서 b를 크게 만들수록 연산의 횟수는 점점 줄어들 것이다.
그러나 일정 이상 b가 커지면 b를 더이상 증가시키는 것이 손해인 순간이 온다 (ex a=12,b=7 : a=12,b=8 의 결과는 동일하다.)

3. 그러므로 b를 증가시키는 것이 손해가 되는 순간이 i일 때,
정답은 i-1만큼 b를 증가시켰을때이다.

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int tc,a,b;
 
int sol(int a,int b){
    int ret=0;
    while(a!=0){
        a/=b;
        ret++;
    }
    return ret;
}
 
int main(){
    scanf("%d",&tc);
    while(tc--){
        int ans=1e8;
 
        scanf("%d%d",&a,&b);
 
        int prev=1e8;
        for(int i=0;;i++){
            if(b+i==1) continue;
 
            int t = sol(a,b+i);
            t+=i;
            if(t>prev) break;
            prev=t;
        }
        printf("%d\n",prev);
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round701-Div.2/A.cpp

https://codeforces.com/contest/1472/problem/A

[난이도] Div.3
[유형] 수학

[풀이]
2^(W가 2로 나눠지는 횟수) * 2^(H가 2로 나눠지는 횟수) 가 최대 자를 수 있는 조각임을 알 수 있다.

#include <cstdio>
using ll = long long;
int tc,H,W;
ll N;
int main(){
    scanf("%d",&tc);
    while(tc--){ 
        scanf("%d%d%lld",&W,&H,&N);
        int wc=1,hc=1;
        while(W%2==0){
            wc*=2;
            W/=2;
        }
        while(H%2==0){
            hc*=2;
            H/=2;
        }
        if(wc*hc >= N) puts("YES");
        else puts("NO");
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round693-Div.3/A.cpp

https://www.acmicpc.net/problem/2487

[난이도] Gold3
[유형] 수학

[풀이]
각 카드가 몇번에 섞기 만에 원래 자리로 돌아올 수 있는지를 구하고,
0번인 카드를 제외한 이들의 최소공배수를 구하면 이것이 수열의 궤적이다.
각 카드마다 섞기 횟수를 구하면 시간초과가 나기 때문에
만약 1->3->5->1 이라면 1,3,5 전부 3번만에 원래 자리로 돌아오기 때문에 1을 구하면서
3,5도 같이 3으로 기록해줘야 한다.

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/2487.cpp

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;
int N,v[20001],cycle[20001];
ll gcd(ll a,ll b){
    ll c;
    if(a<b) swap(a,b);
    while(b!=0){
        c=a%b;
        a=b;
        b=c;
    }
    return a;
}
ll lcm(ll a,ll b){
    return (a*b)/gcd(a,b);
}
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) scanf("%d",&v[i]);
    for(int i=1;i<=N;i++){
        if(cycle[i]!=0) continue;
        int k=i,cnt=1;
        vector<int> l;
        l.push_back(k);
        if(v[k]==i) cnt=0;
        while(v[k]!=i){
            k=v[k];
            l.push_back(k);
            cnt++;
        }
        for(int w : l) cycle[w]=cnt;
    }
    sort(v+1,v+1+N);
    ll ans=1;
    for(int i=1;i<=N;i++) {
        if(cycle[i]!=0) ans = lcm(ans,cycle[i]); 
    }
    printf("%lld",ans);
}

https://www.acmicpc.net/problem/15897

[난이도] Gold3
[유형] 수학

[풀이]
6번째 라인을 잘 살펴보면 i가 (1~N) 일때 모든 1+(N-1)/i의 합임을 알 수 있다.
그런데 N범위 10^9이므로 O(N)으로는 시간내에 풀수가 없다.

(N-1)/i 의 값이 똑같은 i들을 한번에 넘어가야한다.

이 과정은 아래 코드로 구현하였다.

    for(long long i=1,cur=N-1;i<N;i+=d,cur=(N-1)/i){
        d = ((N-1)%i)/((N-1)/i)+1;
        ans+=cur*d;
    }

각 변수의 의미는 다음과 같다.
i: (문제의 4번째 라인에서 i와 같은 의미)
cur: 현재 정답에 추가되어야 할 몫의 값 ((N-1)/i의 값)
d: cur과 다른 몫을 가지게 되는 i값이 i+d일때의 d값
(cur의 몫을 가지는 i는 총 d개이다. 그러므로 cur*d만큼을 ans에 더해준 것을 알 수 있다.)

d = ((N-1)%i)/((N-1)/i)+1 <= 이 로직으로 d를 구할 수 있는 이유는 다음과 같다.
현재 몫은 (N-1)/i이고, 나머지는 (N-1)%i이다.
i가 1씩 증가함에 따라 이 나머지는 (N-1)/i씩 줄어들게 된다.
그러므로 i에 ((N-1)%i)/((N-1)/i) 만큼을 더했을 때가 마지막으로 몫이 (N-1)/i인
순간이고, 여기서 i에 1을 더하게 되면 몫이 최초로 (N-1)/i보다 작아지게 된다. => (N-1)/i > (N-1)/(i+d)

글로 설명하기는 어렵기 때문에 각자가 잘 찾을 수 있는 규칙을 찾아보는 것을 추천한다.

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/15897.cpp

#include <cstdio>
long long N,ans,d;
int main(){
    scanf("%lld",&N);
    for(long long i=1,cur=N-1;i<N;i+=d,cur=(N-1)/i){
        d = ((N-1)%i)/((N-1)/i)+1;
        ans+=cur*d;
    }
    printf("%lld",ans+N);
}