[Codeforces 1011E] Border

[Codeforces 1011E] Border - 1800

문제 설명 : 

각 금액별 banknote가 충분히 많이 있다. 이 banknote들을 적당히 조합하여 만들 수 있는 정수들의 경우의 수를 구하는 문제이다.

풀이 : 

베주 항등식을 활용하는 문제이다. 베주 항등식이란 두개 이상의 정수들의 최대공약수는 그 수들의 정수 곱으로 반드시 표현될 수 있다는 이론이다. 증명은 어려우니깐 패스하고 그냥 가능한가보다 라고 생각하겠다. 이 문제의 관심사는 각 banknote의 금액(a_i)를 k로 나머지 취한 값들을 적절하게 정수배하여 만들 수 있는 모든 금액의 경우의 수를 구하는 것이다. 

주의할 점 : 

-

배운 점 : 

n개의 수들을 적절히 정수배한 값의 합의 모든 경우의 수를 구하기 위해서 베주 항등식을 활용하였다. 이 이론에 의하면 n개의 수들의 최대공약수를 정수배하면 모든 경우의 수를 구할 수 있다.

코드 :

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<assert.h>
#include<stdlib.h>
#include<stack>
using namespace std;
/*********************Contest Template***********************/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<int,int> Cord;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(0);
struct S{
    int a,b; S(){}S(int _a,int _b){
        a=_a; 
        b=_b;
    }
    const bool operator<(const S &o) const{
        return a<o.a;
    }
};
priority_queue<int,vector<int>,greater<int>> mpq;
#define SPACE 0
#define NL 1
inline void showAll(vector<int> &v,int NL_or_space){ 
    //0 is space, 1 is NL
    for(int &here:v){
        printf("%d",here);
        printf("%c",(NL_or_space)?'\n':' ');
    }
}
/*********************Contest Template***********************/
const int SIZE= 100009;
 
int getGCD(int a,int b){
    return (b==0)?a:getGCD(b,a%b);
}
 
int main(){
    int n,k;    scanf("%d %d",&n,&k);
 
    int G=0;
    for(int i=1 ; i<=n ; i++){
        int inp;    scanf("%d",&inp);
        G=getGCD(G,inp);
    }
 
    set<int> ans;
    for(ll i=1 ; i<=k ; i++)
        ans.insert((i*G)%k);
 
    printf("%d\n",ans.size());
    for(int here:ans) printf("%d ",here);    
 
    return 0;
}