출처: https://cses.fi/problemset/task/1618

문제 설명

Your task is to calculate the number of trailing zeros in the factorial n!n!.

For example, 20!=2432902008176640000 and it has 4 trailing zeros.

입력

The only input line has an integer n.

출력 양식

Print the number of trailing zeros in n!.

입력 예

20

출력 예

4

제약조건

1 <= n <= 10^9

문제 풀이

팩토리얼에서 뒤에 나오는 0의 갯수는 N보다 작은 수중에서 곱해지는 5나 5의 거듭제곱수들이 몇번인가와 같다. 그래서, 5로 계속 나누면서 나오는 수들을 누적해서 출력한다. 엄밀하게는 2와 2의 거듭제곱수들의 빈도수와 비교해야 한다.

프로그램 내용

더보기 
#define MAX_N 1000000000

int main()
{
    int N;
    cin >> N; 

    /// count number of 5 less than N
    int count_5=0;
    int div=1;
    long base = N;

    while(div != 0)
        div = base / 5;
        count_5 += div;
        base = div;

	cout << count_5 << endl;

 

Introductory problems ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 1. Palindrome Reorder (1755)  (0) 2019.09.23
CSES 1. Coin Piles (1754)  (0) 2019.09.23
CSES 1. Bit Strings (1617)  (0) 2019.09.22
CSES 1. Two Knights (1072)  (0) 2019.09.22
CSES 1. Two Sets (1092)  (0) 2019.09.21

출처: https://cses.fi/problemset/task/1617 

문제 설명

Your task is to calculate the number of bit strings of length n.

For example, if n=3, the correct answer is 8, because the possible bit strings are 000, 001, 010, 011, 100, 101, 110, and 111.

입력

The only input line has an integer n.

출력

Print the result modulo 10^9+7 

입력 예

3

출력 예

8

제약조건

1 <= n <=10^6

문제 풀이 

n - bit 의 문자열은 2^n 만큼의 다른 정보를 가진다. 입력 받은 N에 대해서 2^N mod Base 연산을 하고, 결과를 출력한다. 단, Base = 1e9 +7 이다. 

프로그램 내용

더보기 
#define MAX_N 1000000
#define BASE 1000000007 /// BASE is prime number

int modpow(int n)
{
    long long m = 1e9+7; 

    if (n == 0) return 1%m;

    long long u = modpow(n/2);

    u = (u*u) %m ;

    if (n%2 == 1) u = (u*2)%m;

    return u;
};

int main()
{
    int N;			/// number of bits    

    cout << modpow(N) << endl;

 

Introductory problems ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 1. Coin Piles (1754)  (0) 2019.09.23
CSES 1. Trailing Zeros (1618)  (0) 2019.09.23
CSES 1. Two Knights (1072)  (0) 2019.09.22
CSES 1. Two Sets (1092)  (0) 2019.09.21
CSES 1. Number Spiral (1071)  (0) 2019.09.21

출처: https://cses.fi/problemset/task/1072

문제 설명

Your task is to count for k=1,2,…,n the number of ways two knights can be placed on a k×k chessboard so that they do not attack each other.

입력 

The only input line contains an integer n.

출력

Print n integers: the results.

입력 예

8

출력 예

0
6
28
96
252
550
1056
1848

제약조건

1 <= n <= 10000

문제 풀이 

N x N 체스보드에 두개의 knight를 올려 놓는 방법의 경우의 수는 첫번째 나이트를 놓을 수 있는 경우의 수(NxN)와 두번째 나이트를 올려 놓을 수 있는 경우의 수 (NxN-1)를 곱한 만큼이다. 이 중에서 두개의 knight가 서로 공격할 수 있는 경우는 3x2 혹은 2x3의 작은 보드의 마주보는 귀퉁이에 나이트들이 위치하는 경우이다. 이 작은 보드의 수는 2x3의 경우는 (N-1)(N-2), 3x2의 경우는 (N-2)(N-1) 이다. 4개의 귀퉁이가 있으므로 4[(N-2)(N-1)+(N-1)(N-2)]를 전체에서 제외하면 된다. 문제에서는 2개의 Knight 색깔을 구분하지 않으므로, 계산한 경우의 수/2를 하면 답이다.

W    
    B
혹은 
W  
   
  B

프로그램 내용

더보기 
#define MAX_N 10000

int main()
{

    for (long i=1;i<= N;i++)
        unsigned long long k_case;
        k_case = i*i*i*i - 9*i*i + 24*i -16;

        if (i==1)
            cout << 0 << endl;
        else
            cout << k_case/2 << endl;

 

Introductory problems ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 1. Trailing Zeros (1618)  (0) 2019.09.23
CSES 1. Bit Strings (1617)  (0) 2019.09.22
CSES 1. Two Sets (1092)  (0) 2019.09.21
CSES 1. Number Spiral (1071)  (0) 2019.09.21
CSES 1. Permutations (1070)  (0) 2019.09.19

+ Recent posts

티스토리툴바