POI2014 Solar Panels

Solar Panels
POI2014
に言及
複数組の質問で,x∈[L 1,R 1],y∈[L 2,R 2]を質問するたびにgcd(x,y)の最大値
解
1.答えをdにするには、⌊L 1−1−1 d⌋lfloorfrac{L 1−1}{d}rfloor⌊dL 1−1⌋<⌊R 1 d⌋lfloorfrac{ R 1}{d}rfloor⌊dR 1⌋&&⌊L 2−1 d⌋lfloorfrac{ L 2}{d}rfloor⌊d−L 1⌊1−1 8971;<⌊R 2 d⌋lfloorfrac{R 2}{d}rfloor⌊dR 2⌋
2.問題は、最大のdが上記の条件を満たすことである
3.観察式子⌊L 1−1 d⌋lfloorfrac{ L 1−1}{d}rfloor⌊dL 1−1⌋<⌊R 1 d⌋lfloorfrac{ R 1}{d}rfloor⌊dR 1⌋&&⌊L 2−1 d⌋lfloorfrac{ L 2}{d}rfloor⌊d−L 2−1⌋<⌊R 2 d⌋lfloorfrac{R 2}{d}rfloor⌊dR 2⌋これは下向きに整頓されているので、dを選ぶときは、できるだけR 1,R 2を整頓できるようにしてR 1,R 2を整頓し、R 2の損失はできるだけ少なくする
4.一つのdを列挙し、そのdの場合、そのdを最初から見つけ出すと、整除すれば、最大でどれだけのd’d’=min(R 1/(R 1/d)、R 2/(R 2/d))が得られるかを示す ， ⌊L 1−1 d′⌋lfloorfrac{L 1−1}{d′}rfloor⌊d′L 1−1⌋<⌊R 1 d′⌋lfloorfrac{ R 1}{d′}rfloor⌊d′R 1⌋&&⌊L 2−1 d′⌋lfloorfrac{ L 2−1}{d′}rfloor⌊d′L 2−L 2−1−−1 d′⌋&&&⌊L 1 d′′⌋lfloorfrac{ L 2}{d′}rfloor 1⌋<⌊R 2 d′⌋lfloorfrac{R 2}{d'}rfloor⌊d′R 2⌋,ans=max(ans,d')
そしてd=d’+1、そのまま次のブロックへ
5.d’が発見されるたびに、d’がR 1によって除去されるか、またはd’がR 2によって除去される.総複雑度はO(R 1+R 2sqrt{R 1}+sqrt{R 2}R 1+R 2)である.
具体コード

#include
using namespace std;
int q,ans;
int L1,R1,L2,R2;
void rd(int &res){
	res=0;
	char c;
	while(c=getchar(),c<48);
	do res=(res<<3)+(res<<1)+(c^48);
	while(c=getchar(),c>47);
}
int main() {
    rd(q);
    while(q--) {
    	rd(L1),rd(R1),rd(L2),rd(R2);
        ans=0;
        L1--,L2--;
        if(R1>R2)swap(L1,L2),swap(R1,R2);
        for(int i=1,j; i<=R1; i=j+1) {
            j=min(R1/(R1/i),R2/(R2/i));
            if(R1/j>L1/j&&R2/j>L2/j)ans=j;
        }
        printf("%d
",ans);
    }
    return 0;
}