UVA 1642 Magical GCD（经典gcd）

题意：给你n（n<=100000）个正整数,求一个连续子序列使序列的所有元素的最大公约数与个数乘积最大

题解：我们知道一个原理就是对于n+1个数与n个数的最大公约数要么相等，要么减小并且减小至少一半（至少少了一个因子）

　　　因此所有子串gcd的总种类数最多只有n*log(a(数字大小))个

　　　我们枚举每个点计算以这个点为结束点的所有后缀，利用dp的思想通过前一次计算的最多log(a)个gcd计算出此时也是最多log(a')个gcd

import java.util.Scanner;

public class Main{

    static int Max=100010;

    static Long[] num=new Long[Max];

    static Long[][] gcd=new Long[Max][100];//后缀的gcd值只可能有loga种

    static int[][] len=new int[Max][100];//对应位置的长度

    public static Long Gcd(Long i,Long j) {

        if(j==0)

            return i;

        else

            return Gcd(j, i%j);

    }

    public static void main(String[] args) {

        int t,n;

        Scanner sc=new Scanner(System.in);

        t=sc.nextInt();

        while(t!=0){

            n=sc.nextInt();

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

                num[i]=sc.nextLong();

            }

            System.out.println(SolveGcd(n));

            t--;

        }

    }

    private static Long SolveGcd(int n) {

        Long res=0L;

        int coun,pre=0;

        //从第一个开始计算后缀

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

            coun=0;

            gcd[i][coun]=num[i];

            len[i][coun]=1;

            res=Math.max(res,num[i]);

            coun++;

            //使用上一层后缀计算此层，并且注意删除相同的值

            for(int j=0;j<pre;++j){

                gcd[i][coun]=Gcd(num[i], gcd[i-1][j]);

                len[i][coun]=len[i-1][j]+1;

                res=Math.max(res, gcd[i][coun]*len[i][coun]);

                if(gcd[i][coun].equals(gcd[i][coun-1])){//gcd相同时存总个数

                    len[i][coun-1]=len[i][coun];

                }else{

                    coun++;

                }

            }

            pre=coun;

        }

        return res;

    }

}

巴特西

UVA 1642 Magical GCD（经典gcd）

最新文章

热门文章