[백준,c++] 23977번 - To Find Password

문제

23977번: To Find Password

 

코드

#include <iostream>
#include <vector>
#define ll long long

using namespace std;


ll gcd(ll a, ll b){
    if(b==0) return a;
    else return gcd(b,a%b);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    ll N,K; cin>>K>>N;
    
    vector<ll>v;
    for(int i=0; i<N; i++){
        ll num; cin>>num;
        v.push_back(num);
    }
    
    ll num = v[0];
    ll lcm_val = 0;
    
    for(int i=0; i<N; i++){
        lcm_val = (num*v[i]) / gcd(num,v[i]);
        num = lcm_val;
    }
    cout<<num-K;
    
}

 

풀이

일단 문제를 먼저 살펴보면 규칙은 다음과 같습니다.

• 정수 K와 정수 N개로 이루어진 배열 A가 주어진다.
• 비밀번호를 배열 A의 원소들로 각각 나누었을 때, 나누는 수와 그 나머지의 차이는 K로 동일하다.
• 비밀번호는 항상 존재하며, 두 번째 규칙을 만족하는 수 중 가장 작은 양의 정수이다.

입출력 예제를 살펴보면 아래와 같습니다.

입력
4 3
9 8 7

 

출력
500

위 입출력 예제에서 아래와 같은 규칙으로 비밀번호를 찾아내야 합니다.

• 500(구해야 할 수) % 9 = 5
• 500(구해야 할 수) % 8 = 4
• 500(구해야 할 수) % 7 = 3
• 위 값들 9 - 5, 8-4, 7-3 은 각각 4, 4, 4로 전부 동일하다는 규칙으로 해당 500이라는 비밀번호 숫자를 구할 수 있습니다.

이 문제는 각각의 주어지는 입력값들의 최소공배수를 구해 K를 빼주기만 하면 됩니다.