|
|
back to boardMy AC Code Posted by Neptun 26 Oct 2007 08:56 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; } |
|
|