专栏文章

P11312 神奇的小江鸟

RRt__
P11312题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mir076c1
此快照首次捕获于
2025/12/04 13:36
3 个月前
此快照最后确认于
2025/12/04 13:36
3 个月前
查看原文
P11312 神奇的小江鸟

题意简述

给定 nn 个区间 [li,ri][l_i, r_i]，求出是否
∃G≥k,G=gcd⁡i=1nxi∈[li,ri]\exists G \ge k, G = \gcd_{i = 1}^nx_i\in [l_i, r_i]
若存在，则输出Yes和每个 xix_i 的值；否则，输出No。

思路（考场）

观察部分分：
  • k=1k=1：
    直接输出所有区间内的任意一个位置
  • n≤10,ri−li+1≤5n\le 10,r_i - l_i + 1 \le 5；
    直接 DFS 暴力搜索
  • ri<=103r_i <= 10^3
    类似埃氏筛的方法，把 GG 从 kk 往大枚举，kk 的倍数就筛去不用再判断了。

代码

CPP
#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;
}

思路（正解）

当所有区间长度都 ≥k\ge k 时，一定都可以选到。所以我们直接把所有区间内的合法情况输出就可以。
当存在区间的长度 <k< k 时，我们可以先按区间长度排序，保证第一个区间一定合法，这样子我们就可以把第一个区间的 k−1k - 1 个数的所有 ≥k\ge k 因数都存到一个集合里，并依次判断他是否可以满足所有集合。（1∼1091\sim 10^9 的数里面最多只有 99 个质因数，所以因数个数也很少，可以通过）

代码

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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...