BZOJ 3834 [Poi2014]Solar Panels 数学

题意: n组询问，每次问smin<=x<=smax, wmin<=y<=wmax时gcd(x, y)的最大值。 解析: md以前有个结论忘了结果这题坑我30分钟+ 我们显然可以找到一个结论。 令gcd(x,y)=z; 那么显然有(smin-1)/z

;int n;int main(){scanf(“%d”,&n);for(int i=1;i<=n;i++){int x1,y1,x2,y2;scanf(“%d%d%d%d”,&x1,&y1,&x2,&y2);int ans=-1;int la;for(int i=1;i<=y1&&i<=y2;i=la+1){la=min(y1/(y1/i),y2/(y2/i));if(y1/la>(x1-1)/la&&y2/la>(x2-1)/la)ans=max(ans,la);}printf(“%d\n”,ans);}}

，游手好闲会使人心智生锈