はまやんはまやんはまやん

hamayanhamayan's blog

約比 [yukicoder No.736]

https://yukicoder.me/problems/no/736

前提知識

解法

https://yukicoder.me/submissions/288497

既約分数にする場合を考えると、分母分子の最大公約数で割ると、既約分数にできる。
同様にそれ以上約日できないものにするために、全ての要素の最大公約数で割ることにする。
ユークリッドの互除法で最大公約数を求めて、割って、指定のフォーマットで出力しよう。

int N; ll A[101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    ll g = 0;
    rep(i, 0, N) g = gcd(g, A[i]);
    rep(i, 0, N) {
        if (i) printf(":");
        printf("%lld", A[i] / g);
    }
    printf("\n");
}