It's nearly O(n) and it only uses 0.001 second.
As follows:


#include<stdio.h>
#include<string.h>
#include<math.h>
int n,s;
int f[100001];

int gcd(int a,int b)
{
       if(b==0)  return a;
       return gcd(b,a%b);
}

void work()
{
      int i,j,k,max=0;
      memset(f,0,sizeof(f));
      f[s]=1;
      for(i=s;i<=n;i++){
            if(f[i]){
                 if(i>100) k=gcd(i,100);
                 else k=gcd(100,i);
                 k=i/k;
                 for(j=k;j<=i&&i+j<=n;j+=k){//据说只要加到100%就可以了
                       if(f[i]+1>f[i+j])
                         f[i+j]=f[i]+1;
                 }
                if(f[i]>max)
                  max=f[i];
            }
      }
      printf("%d\n",max);
}
int main()
{
     int i;
     scanf("%d%d",&n,&s);
     work();
     return 0;

}