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)\]
数据范围
变量 | 取值范围 |
---|---|
$n$ | $1\leq n\leq 10^3$ |
$x_0,x_1,y_0,y_1$ | $1\leq x_0,x_1,y_0,y_1\leq 10^9$ |
时空限制
题目编号 | 时间限制 | 空间限制 |
---|---|---|
Luogu P3579 | $1\text{s}$ | $125\text{MiB}$ |
BZOJ 3834 | $?\text{s}$ | $?\text{MiB}$ |
POI2014 S3D3T2 | $?\text{s}$ | $128\text{MiB}$ |
题解
思路
结论:区间 \((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; }
近期评论