[BeiJing2010]取数游戏 game

[BeiJing2010]取数游戏 game

Time Limit:10000MS Memory Limit:65536K
Total Submit:16 Accepted:9
Case Time Limit:1000MS

Description

小 C 刚学了辗转相除法,正不亦乐乎,这小 P 又出来捣乱,给小 C 留了个
难题。
给 N 个数,用 a1,a2…an来表示。现在小 P 让小 C 依次取数,第一个数可以
随意取。假使目前取得 aj,下一个数取ak(k>j),则ak必须满足gcd(aj,ak)≥L。
到底要取多少个数呢?自然是越多越好!
不用多说,这不仅是给小 C 的难题,也是给你的难题。

Input

第一行包含两个数N 和 L。
接下来一行,有 N 个数用空格隔开,依次是 a1,a2…an。

Output

仅包含一行一个数,表示按上述取法,最多可以取的数的个数。

Sample Input

Sample Output

Hint

选取 3个数16、24、6。gcd(16,24)=8,gcd(24,6)=6。

2≤L≤ai≤1 000 000;
30% 的数据N≤1000;
100% 的数据 N≤50 000

Source
额。。这题感觉跟VIJOS上一题一样。。记Dpi表示以i的倍数为结尾的最长长度。。然后Dp一下就可以了。。

#include <algorithm>#include <cstdio>#define rep(i,n) for(int i=0;i<n;i++)const int inf=~0U>>1,maxw=1000000,maxp=10000;using namespace std;int Dp[maxw+1]={},n,L,List[maxp];int main(){ scanf("%d%d",&n,&L); rep(i,n) { int x,tmp=0,c=0; scanf("%d",&x); for(int i=1;i*i<=x;i++) if(x%i==0) { if(i>=L)List=i; if(x/i>=L)List=x/i; } rep(i,c)tmp=max(tmp,Dp[List[i]]);tmp++; rep(i,c)Dp[List[i]]=tmp; } int ans=0; rep(i,maxw+1)ans=max(ans,Dp[i]); printf("%dn",ans);}35 6 7 16 9 24 6

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>