白駿2981号:尋問

9054 ワード
ps Euclidean algorithm cpp math テキストリンク
に質問
白駿2981号:尋問
アイデア
N1 % M = k
N2 % M = k
N3 % M = k
N4 % M = k
...
N2 % M - N1 % M = 0
(N2 - N1) % M = 0
したがって、それぞれの数字の差を求め、その差の最大公約数を求め、求めた最大公約数の公約数を全て出力すればよい!
なお、gcd(a,b)=gcd(a+b,b)は、大きさ順に並べ替えた後、隣接する数字の差だけが必要となる.
ミネラルウォーターを探すときはO(N)ではなくO(√N)です.
コード#コード#
#include <bits/stdc++.h>

using namespace std;

int gcd (int a, int b) {
    if (!b) return a;
    return gcd(b, a%b);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    vector<int> v(n), dif(n-1);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    sort(v.begin(), v.end());
    for (int i = 0; i < n-1; i++) {
        dif[i] = v[i+1] - v[i];
    }

    int g = dif[0];
    for (int x : dif) {
        g = gcd(g, x);
    }

    vector<int> div;
    for (int i = 2; i*i <= g; i++) {
        if (g%i == 0) {
            div.push_back(i);
            if (i*i != g) div.push_back(g/i);
        }
    }
    sort(div.begin(), div.end());
    for (int& x : div) cout << x << ' ';
    cout << g;

    return 0;
}

おしゃべり
2年前に途中で頑張って解答して諦めた問題.
本当に整数じゃないと難しいですねしっかり勉強しなさい
【微信H 5開発】大画面iPhoneでは微信QRコードが認識できない
Ubuntu 19.10低バージョンのMysql 5をインストールします.7.29