[BeiJing2010]取数游戏 game 【水水更健康】

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1978

【算法分析】

看到2<=ai<=10^6。

就可以开个桶暴力了。

公约数首先是约数嘛。。。然后就把他所有的约数搞一下，瞬间AC。

【时间复杂度】O(n * Ai ^ 0.5)

【空间复杂度】O(10^6)

【CODE】

#include int p[1000005];

int main(){ freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    scanf("%d%d",&n,&L);
    for (i=1;i<=n;i++){
        scanf("%d",&x);
        if (x        now=0;
        for (j=1;j*j<=x;j++)
          if (!(x%j)){
            if (j>=L) now>?=p[j];
            if (x/j>=L) now>?=p[x/j];
          }
        now++;
        ans>?=now;
        for (j=1;j*j<=x;j++)
          if (!(x%j)){
            p[j]=now;
            p[x/j]=now;
          }
    }
    printf("%dn",ans);
}