/*之前一直想不通,明白了用时间二分来接近要求的值就清晰了 迫近的值之后来判断哪个是成立的即可 */ #include<stdio.h> #define ll long long int const int MAX=100005; int b; ll m[1005]; int num=0; ll n; ll geshu(ll n) { ll ans=0; int i; for(i=0;i<b;i++) ans+=(n-1+m[i])/m[i]; return ans; } int main() { int t; scanf("%d",&t); while(t--) { int i; scanf("%d%d",&b,&n); for( i=0;i<b;i++) scanf("%d",&m[i]); ll lt=0,rt=MAX*n; while(lt<rt) { ll mid=(lt+rt)>>1; if(geshu(mid)<n) lt=mid+1; else rt=mid; } int flag; flag=geshu(lt-1); int wtf=0; for(i=0;i<b;i++) { if((lt-1)%m[i]==0) { flag++; if(flag==n) { wtf=i+1; break; } } } printf("Case #%d: %d\n",++num,wtf); } return 0; } |
Double click to view unformatted code.