本文主要是介绍HDU 1316 大数二分,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
建素数表 二分查找 练手用了。。
#include "stdio.h"
#include "string.h"
int f[5010][1010];int pk(int a[],int b[])
{int i;if (a[0]>b[0]) return 1;if (a[0]<b[0]) return -1;for (i=a[0];i>=1;i--){if (a[i]>b[i]) return 1;if (a[i]<b[i]) return -1;}return 0;}int fi(int x[],int op)
{int l,r,mid,key;l=1;r=5000;while (l<=r){mid=(l+r)/2;key=pk(x,f[mid]);if (key==1) l=mid+1;else if (key==-1) r=mid-1;else return mid;}if (op==1) return l;if (op==2) return r;
}int main()
{int i,j,lea,leb,keya,keyb;int a[1201],b[1201];char stra[1201],strb[1201];memset(f,0,sizeof(f));f[1][0]=f[1][1]=f[2][0]=f[2][1]=1;for (i=3;i<=5000;i++){for (j=1;j<=f[i-1][0];j++)f[i][j]=f[i-1][j]+f[i-2][j];f[i][0]=f[i-1][0];for (j=1;j<=f[i][0];j++){f[i][j+1]+=f[i][j]/10;f[i][j]%=10;}if (f[i][f[i][0]+1]!=0) f[i][0]++;}// printf("%d\n",f[5000][0]);while (scanf("%s",stra)!=EOF){scanf("%s",strb);if (stra[0]=='0' && strb[0]=='0') break;if (stra[0]=='0') stra[0]='1';a[0]=lea=strlen(stra);b[0]=leb=strlen(strb);for (i=0;stra[i];i++)a[lea-i]=stra[i]-'0';for (i=0;strb[i];i++)b[leb-i]=strb[i]-'0';keya=fi(a,1);keyb=fi(b,2);printf("%d\n",keyb-keya+1);}return 0;}
这篇关于HDU 1316 大数二分的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!