A simple Blog for wyx I've been down the bottle hoping.
3834: [Poi2014]Solar Panels 数论 分块
发表于: | 分类: Oi | 评论:0 | 阅读:54

题目大意
给定$x_1,x_2,y_1,y_2$,求$\max{\gcd(x,y)},x\in[x1,x2],y\in[y1,y2]$

我们假设这个数字是$d$,显然如果想要存在这样的答案当且仅当$[x1,x2]$,中有$d$的倍数,$[y1,y2]$中有$d$的倍数

然后你会发现直接枚举$\lfloor \frac{a}{d} \rfloor$ 就行了,因为这个东西只有$\sqrt{a}$个取值

为什么?以$\sqrt{n}$为界限讨论一下,前面一共有$\sqrt{n}$个数字,后面的数字都小于$\sqrt{n}$,所以不同的个数是$\sqrt{n}$级别的

复杂度就是$Q\sqrt{n}$

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;

inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int main() {
    int Q = read(), a, b, c, d, ans = 1;
    for(int i=1;i<=Q;++i,ans = 0) {
        a = read(), b = read(), c = read(), d = read();
        for(int i=1,last;i <= b && i <= d;i=last+1) {
            last = min(b/(b/i),d/(d/i));
            if(b/last>(a-1)/last&&d/last>(c-1)/last) ans=max(ans,last); 
        }
        printf("%d\n",ans);
    }
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP