P9652 『GROI-R2』 紫水晶

渡墨残殇 · 2023-09-27 15:25:55 · 题解

对于这个题我要先说一句，不能被样例迷惑，因为决定这个题的关键只是再最后两个数而已。

另外很早之前有个月赛的题和这个很像都是要还原原来的数列。

P 8278

分析

其实这个题和最大公因数和最小公倍数关系不大，就只是需要两个概念即可。

• n$ 和 $1$ 的最大公因数是 $1$,最小公倍数是 $n

做法

1. n\leq2

输出两个 x 即可。

2. n\geq3

• 最大公因数

把前面的全赋值为 1，前面的空全部为一堆 1 加在一块，然后让最后两个空均输出 sum-(n-2) 即可。

• 最小公倍数

一样，把前面的全赋值为 1，前面的空全部为一堆 1 加在一块，最后只需要留出来一个空输出 sum-(n-2) 即可。

另外当 n-1\gt x 时，直接输出 -1，因为此时所有均为 1 相加都不满足题意。

代码

#include<bits/stdc++.h>
using namespace std;
int a[5000100];
void Lcd(int l,int r,int sum)
{
  if(sum<r-1){cout<<"-1\n";return ;}
  if(r==2){
    cout<<sum<<" "<<sum<<"\n";return ;}
  int po=sum-(r-2);
  for(int i=1;i<=r-2;i++){
    cout<<1<<" ";
  }cout<<po<<" "<<po<<"\n";
}
void Lcm(int l,int r,int sum)
{
  if(sum<r-1){cout<<"-1\n";return ;}
  if(r==2){
    cout<<sum<<" "<<sum<<"\n";return ;}
  int po=sum-(r-2);
  for(int i=1;i<=r-1;i++){
    cout<<1<<" ";
  }cout<<po<<"\n";
}
int q;
int main ()
{
    cin>>q;
    while(q--)
    {
      int op,n,x;cin>>op>>n>>x;
      if(op==1)
      {
        Lcd(1,n,x);
      }
      else
      {
        Lcm(1,n,x);
      }
    }
}