ABC125 - C - GCD on Blackboard(300点)

問題概要

問題へのリンク

$N$ 個の整数 $A_1$,$A_2$,...,$A_N$が並んでいる。$N$個の整数からある一つの値を任意の値に書き換える。
書き換えた後の $N$ 個の整数の最大公約数の最大値を求めよ。

制約条件

• 入力は全て整数である。
• $2≤N≤10^5$
• $1≤A_i≤10^9$

考えたこと

この問題において「ある値を書き換える」という行為は「ある値を排除する」と同義。最大公約数の最大値を求めるので書き換える値はその値を排除した$N-1$個の整数の最大公約数の倍数である任意の値に書き換えればよいので。

例えば入力例1だと 7 6 8 で答えは7を書き換えて2となります。この時7をどんな値に書き換えるかは2の倍数であればなんでもいいわけです。

となると、$N$個の整数の値についてその値がない場合の最大公約数をそれぞれ求めて、最大値を求めればよい。これを毎回最大値を求めていたら計算時間は圧倒的にオーバーするので、累積和的なのりで、ある値 $A_i$ に対して区間$0$ ~ $i-1$と$i+1$ ~ $n-1$の最大公約数をそれぞれ予め求めておく。

こうすれば計算量 $O(N)$ で答えを求めることが可能。

累積和的な考え方についてはTwitterで共有されていた以下の図がすごくわかりやすいです。
https://twitter.com/armeria_betrue/status/1122134567765233665

解答

c.cs

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args) {
        int n = int.Parse(Console.ReadLine());
        List<int> a = Console.ReadLine().Split().Select(int.Parse).ToList();
        Console.WriteLine(solve(n, a));
    }
    static int solve(int n, List<int> a) {
        int[] lgcd = new int[n-1];
        lgcd[0] = a[0];
        for(int i = 1; i < n-1; i ++) {
            lgcd[i] = Gcd(a[i],lgcd[i-1]);
        }
        a.Reverse();
        int[] rgcd = new int[n-1];
        rgcd[0] = a[0];
        for(int i = 1; i < n-1; i ++) {
            rgcd[i] = Gcd(a[i],rgcd[i-1]);
        }
        a.Reverse();
        int[] ans = new int[n];
        ans[0] = rgcd[n-2];
        ans[n-1] = lgcd[n-2];
        for(int i = 1; i < n-1; i ++) {
            ans[i] = Gcd(lgcd[i-1], rgcd[n-2-i]);
        }
        return ans.Max();
    }
    static int Gcd(int a, int b) {
        if (a < b) return Gcd(b, a);
        while (b != 0) {
            var tmp = a % b;
            a = b;
            b = tmp;
        }
        return a;
    }
}