分析

首先我们发扬人类智慧

感觉最大公因数不会太大，所以直接从 k 枚举到 10^6 ，判断每个区间是否符合，在未加强数据时，这个代码可以得到 100 分的好成绩。

贴一下主要部分的代码。

for(int i=k;i<=1000000;i++){
  fl=0;
  for(int j=2;j<=n;j++) if(a[j].x>a[j].y||(a[j].x%i&&a[j].y%i&&a[j].x/i==a[j].y/i)){
    fl=1;//有区间不符合条件
    break;
  }
  if(!fl){//所有区间符合条件直接统计答案
    c.clear();
    puts("Yes");
    for(int j=1;j<=n;j++) c.push_back((a[j].x/i+(bool)(a[j].x%i))*i);
    for(int x:c) printf("%d ",x);
    putchar('\n');
    break;
  }     
}

但是加强数据后只能获得 65 分，我们考虑如何继续发扬人类智慧。

我们可以猜测由于答案比较大，所以每个区间都比较分散，所以可以从选择一个最小的右端点,枚举 k 到这个右段点的每一个数，然后判断每个区间是否符合，最后可以获得 85 分的好成绩。

贴一下重点代码。

struct ha{
    int x,y,id;
};
ha a[10005];
inline bool cmp1(ha &a,ha &b){
    return a.y<b.y;
}
inline bool cmp2(ha &a,ha &b){
    return a.id<b.id;
}
sort(a+1,a+1+n,cmp1);
if(a[n].x>a[n].y){//特判
  puts("No");
  continue;
}
fl=1;
for(int i=k;i<=a[1].y;i++){
  fl=0;
  for(int j=1;j<=n;j++) if((a[j].x%i&&a[j].y%i&&a[j].x/i==a[j].y/i)){
    fl=1;//不符合条件
    break;
  }
  if(!fl){//符合条件
    c.clear();
    puts("Yes");
    sort(a+1,a+1+n,cmp2);
    for(int j=1;j<=n;j++) c.push_back((a[j].x/i+(bool)(a[j].x%i))*i);
    for(int x:c) printf("%d ",x);
    putchar('\n');
    break;
  } 
}
if(fl) puts("No");

我们继续发扬人类智慧。

由于只有一个点错了，而且这个点是 Subtask 2 的原来能过的点，所以我们只需要进行数据分治： n \le 10 用第一种方法，剩下情况用第二种方法。

AC 代码

#include <bits/stdc++.h>
using namespace std;
struct ha{
    int x,y,id;
};
ha a[10005];
inline bool cmp1(ha &a,ha &b){
    return a.y<b.y;
}
inline bool cmp2(ha &a,ha &b){
    return a.id<b.id;
}
int t,n,k;
bool fl;
vector<int> c;
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++){
            scanf("%d%d",&a[i].x,&a[i].y);
            a[i].id=i;
            a[i].x=max(a[i].x,k); 
        } 
        if(n<=10){
            for(int i=k;i<=1000000;i++){
                fl=0;
                for(int j=2;j<=n;j++) if(a[j].x>a[j].y||(a[j].x%i&&a[j].y%i&&a[j].x/i==a[j].y/i)){
                    fl=1;
                    break;
                }
                if(!fl){
                    c.clear();
                    puts("Yes");
                    for(int j=1;j<=n;j++) c.push_back((a[j].x/i+(bool)(a[j].x%i))*i);
                    for(int x:c) printf("%d ",x);
                    putchar('\n');
                    break;
                }   
            }
            if(fl) puts("No");
        }
        else{
            sort(a+1,a+1+n,cmp1);
            if(a[n].x>a[n].y){
                puts("No");
                continue;
            }
            fl=1;
            for(int i=k;i<=a[1].y;i++){
                fl=0;
                for(int j=1;j<=n;j++) if((a[j].x%i&&a[j].y%i&&a[j].x/i==a[j].y/i)){
                    fl=1;
                    break;
                }
                if(!fl){
                    c.clear();
                    puts("Yes");
                    sort(a+1,a+1+n,cmp2);
                    for(int j=1;j<=n;j++) c.push_back((a[j].x/i+(bool)(a[j].x%i))*i);
                    for(int x:c) printf("%d ",x);
                    putchar('\n');
                    break;
                } 
            }
            if(fl) puts("No");  
        }
    }
    return 0;
}