Codeforces Round #209 (Div. 2) D. Pair of Numbers

74 阅读 0 评论 49 点赞

我是靠谱客的博主迅速月饼，最近开发中收集的这篇文章主要介绍Codeforces Round #209 (Div. 2) D. Pair of Numbers，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

简单数学

在给出的数列里面，求出一个最长连续数列，是它们的最大公约数在这里面。

代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>

#define LEN 300010

using namespace std;

int a[LEN], ans[LEN];

int main() {
    int n;
    while(scanf("%d", &n)!=EOF) {
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        int l, r, cnt = 0, tmp = 0;
        for(int i = 1; i <= n; ) {
            l = r = i;
            while(l && a[l]%a[i] == 0)
                l--;
            while(r <= n && a[r]%a[i] == 0)
                r++;
            i = r;
            r = r - l -2;
            if(r > tmp) {
                cnt = 0;
                tmp = r;
            }
            if(r == tmp)
                ans[cnt++] = l + 1;
        }
        printf("%d %dn", cnt, tmp);
        for(int i = 0; i < cnt; i++) {
            if(!i)
                printf("%d", ans[i]);
            else
                printf(" %d", ans[i]);
        }
        puts("");
    }
    return 0;
}