유클리드 호제법

A와 B가 주어졌을때 두 수의 최대공약수 구하기

    int GCD(int A,int B){

        if(A%B==0){
        return B;} 

     // a에서 b를 나눈 나머지가 0이면 b를 리턴함

    else{

    return GCD(B,A%B);

     // 그게아니라면 GCD(B,A%B)를 리턴함
    }}

이렇게하면 결국 최대공약수를 리턴한다.

적은 숫자를 v[i]라고 해보자.

v[i] = 몫[i] * M - 나머지1 이다.

v[i-1] = 몫[i-1] * M - 나머지2 이다.

두 식을 빼주면
v[i]-v[i-1] = (몫[i]-몫[i-1]) * M + (나머지1-나머지2)
이다.

하지만 우리는 나머지가 같은 경우를 찾고있으니
v[i]-v[i-1] = (몫[i]-몫[i-1]) * M 가 성립하는 식을 찾으려한다.

모든 v[i] - v[i-1]을 구한다음 그 수들의 최대공약수를 찾은다음,

최대공약수의 약수를 구한다면 그게 답이되지 않을까?

    #include<bits/stdc++.h>
    #define endl '\n'
    #define FASTio ios_base ::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
    #include <vector>
    #include <algorithm>
    using namespace std;

최대공약수 구하는 함수

    int GCD(int a,int b){

        if(a%b==0){
            return b;
        }

        return GCD(b,a%b);


    int n; // 입력받을 숫자개수
    int a; 
    vector <int> num;
    vector <int> v;
    vector <int> answer;
    int main(){
        FASTio; 
        cin >> n; // 입력받을 숫자입력

        for(int i=0;i<n;i++){
            cin >> a;	
            num.push_back(a); // 숫자입력 (n개만큼) 
        } 

        sort(num.begin(),num.end());// 숫자 정렬

입력한 숫자들의 차를 v에 저장

    for(int i=0;i<n-1;i++){
        v.push_back(num[i+1]-num[i]);

    }
 

    sort(v.begin(),v.end());
    

v에 저장한 수들의 최대공약수 구하기

    int gcd=v[0];

    for(int i=0;i<n-2;i++){

        gcd = GCD(gcd,v[i+1]);
    }

최대공약수 gcd의 약수를 구한다.

    for (int i = 2; i*i<= gcd; i++) {
            if (gcd % i == 0) {
                answer.push_back(i);
                answer.push_back(gcd/i);
            }
        }
        // 약수 구하기 

        answer.push_back(gcd);
        sort(answer.begin(), answer.end());

        answer.erase(unique(answer.begin(), answer.end()), answer.end());
        // 중복 제거

약수 출력

        for (int i = 0; i < answer.size(); i++) {
            cout << answer[i] << " ";
        }


        return 0;
    }