「题解」「POI2014」PAN-Solar Panels

POI2014 Stage 3 Day 3 T2，一道简单的 数学 题目，要用到 数论分块。

题目链接：Luogu P3579/BZOJ 3834/POI2014 S3D3T2。

题目

题目描述

\(n\) 组数据，求
\[\max _ {x\in[x _ 0,x _ 1],y\in[y _ 0,y _ 1]}\gcd(x,y)\]

数据范围

时空限制

题解

思路

结论：区间 \((l,r]\) 中出现 $n$ 的倍数的充要条件是
\[\lfloor\frac{r}{n}\rfloor>\lfloor\frac{l}{n}\rfloor\]

于是可以枚举 \(i\)，看是否在两段区间内都出现过。可以通过枚举商将时间复杂度将至 \(\Theta(n\sqrt{a})\)。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg bool f=false;
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return f?-res:res;
}

int a,b,c,d;

int main(void){
    reg int T=read();
    while(T--){
        a=read(),b=read(),c=read(),d=read();
        if(c<a){
            swap(a,c);
            swap(b,d);
        }
        if(c<=b)
            if(d<=b)
                printf("%d\n",d);
        else
            printf("%d\n",b);
        else{
            reg int last,ans=1;
            for(reg int i=1;i<=min(b,d);i=last+1){
                last=min(b/(b/i),d/(d/i));
                if(b/last>(a-1)/last&&d/last>(c-1)/last)
                    ans=last;
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}

相关题目

• 「题解」「POI2014」卡片 Card。