P11312 神奇的小江鸟

Rt__ · 2024-11-25 09:12:39 · 题解

P11312 神奇的小江鸟

题意简述

给定 n 个区间 [l_i, r_i]，求出是否

\exists G \ge k, G = \gcd_{i = 1}^nx_i\in [l_i, r_i]

若存在，则输出Yes和每个 x_i 的值；否则，输出No。

思路（考场）

观察部分分：

直接输出所有区间内的任意一个位置
直接 DFS 暴力搜索

r_i <= 10^3

类似埃氏筛的方法，把 G 从 k 往大枚举，k 的倍数就筛去不用再判断了。

代码


#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define ld long double

inline ll read(){ ll res = 0, f = 1; char c = getchar(); while(c < '0' || c > '9'){ if(c == '-')f = -1; c = getchar(); } while(c >= '0' && c <= '9'){ res = res 10 + c - '0'; c = getchar(); } return f res; }

const int N = 20010;

struct ii{ ll l, r; int i; bool operator<(const ii & a)const{ if(l == a. l)return r < a. r; return l < a. l; } }a[N];

unordered_map<ll, bool>ma; ll ans[N]; ll n, k; ll mid[N]; ll gcd(ll a, ll b){ if(b == 0)return a; return gcd(b, a % b); } bool dfs(int deep){ if(deep == n + 1){ ll now = mid[1]; for(int i = 2; i <= n; i ++){ now = gcd(now, mid[i]); } if(now >= k){ cout << "Yes" << endl; for(int i = 1; i <= n; i ++)cout << mid[i] << ' '; cout << endl; return 1; } return 0; } for(int i = a[deep]. l; i <= a[deep]. r; i ++){ mid[deep] = i; if(dfs(deep + 1))return 1; } return 0; }

signed main(){ ll t = read(); while(t --){ ma. clear(); n = read(), k = read(); ll maxx = 0; bool flagg = 0; for(int i = 1; i <= n; i ++){ a[i]. l = read(); a[i]. r = read(); if(a[i]. l != a[i]. r)flagg = 1; a[i]. i = i; maxx = max(maxx, a[i]. r); } if(flagg == 0){ ll now = a[1]. l; for(int i = 2; i <= n; i ++){ now = gcd(now, a[i]. l); } if(now >= k){ cout << "Yes" << endl; for(int i = 1; i <= n; i ++)cout << a[i]. l << ' '; cout << endl; } else cout << "No" << endl; continue; } if(k == 1){ cout << "Yes" << endl; for(int i = 1; i <= n; i ++){ cout << a[i]. l << ' '; } cout << endl; continue; } if(n <= 10){ if(!dfs(1))cout << "No" << endl; continue; } sort(a + 1, a + 1 + n); bool flag = 0; for(ll i = k; i <= maxx; i ++){ if(ma[i]){ ma. erase(i); continue; } int idx = 1; for(ll j = 1; j <= maxx / i; j ++){ ma[i j] = 1; while(i j >= a[idx]. l){ if(i j > a[idx]. r)break; ans[a[idx]. i] = i j; idx ++; if(idx > n)break; } if(idx > n)break; if(i * j > a[idx]. r)break; } if(idx == n + 1){ cout << "Yes" << endl; for(int i = 1; i <= n; i ++){ cout << ans[i] << ' '; } cout << endl; flag = 1; break; } } if(!flag)cout << "No" << endl; } return 0; }

## 思路（正解）
当所有区间长度都 $\ge k$ 时，一定都可以选到。所以我们直接把所有区间内的合法情况输出就可以。

当存在区间的长度 $< k$ 时，我们可以先按区间长度排序，保证第一个区间一定合法，这样子我们就可以把第一个区间的 $k - 1$ 个数的所有 $\ge k$ 因数都存到一个集合里，并依次判断他是否可以满足所有集合。（$1\sim 10^9$ 的数里面最多只有 $9$ 个质因数，所以因数个数也很少，可以通过）
## 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'

inline ll read(){
    ll res = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        res = res * 10 + c - '0';
        c = getchar();
    }
    return res * f;
}

const int N = 20010;
struct ii {
    ll l, r;
    int i;
    bool operator<(const ii & a)const{
        return r - l + 1 < a. r - a. l + 1;
    }
}q[N];

ll ans[N];

signed main(){
    ll t = read();
    while(t --){
        ll n = read(), k = read();
        for(int i = 1; i <= n; i ++){
            q[i]. l = read(), q[i]. r = read();
            q[i]. i = i;
        }
        sort(q + 1, q + 1 + n);
        if(q[1]. r - q[1]. l + 1 >= k){
            for(int i = 1; i <= n; i ++){
                ans[q[i]. i] = q[i]. r / k * k;
            }
            printf("Yes\n");
            for(int i = 1; i <= n; i ++){
                printf("%lld ", ans[i]);
            }
            printf("\n");
            continue;
        }
        ii sm = q[1];
        set<ll>s;
        for(ll i = sm. l; i <= sm. r; i ++){
            for(ll y = 1; y <= sqrt(i); y ++){
                if(i % y == 0){
                    if(y >= k)s. insert(y);
                    if(i / y >= k)s. insert(i / y);
                }
            }
        }
        bool have_ans = 0;
        for(auto it = s. begin(); it != s. end(); it ++){
            ll now = *it;
            bool flag = 0;
            for(int i = 1; i <= n; i ++){
                if(q[i]. l / now != q[i]. r / now){
                    ans[q[i]. i] = q[i]. r / now * now;
                }
                else if(q[i]. l % now == 0){
                    ans[q[i]. i] = q[i]. l;
                }
                else if(q[i]. r % now == 0){
                    ans[q[i]. i] = q[i]. r;
                }
                else{
                    flag = 1;
                    break;
                }
            }
            if(!flag){
                printf("Yes\n");
                for(int i = 1; i <= n; i ++){
                    printf("%lld ", ans[i]);
                }
                printf("\n");
                have_ans = 1;
                break;
            }
        }
        if(!have_ans)printf("No\n");
    }
    return 0;
}