小田的gcd构造题解

注:点击标题即可查看原题

题意解析

有两个正整数a和b,你需要使它们满足三个条件:

1.a-b的绝对值大于等于正整数x 2.a+b的绝对值大于等于正整数y 3.a和b的最大公约数(gcd)和正整数z相等

你只需输入一组满足上述条件的数字(a和b)即可,并且a和b均小于5×10^18。

输入描述:输入三个正整数x,y,z

输出描述:输出任意一组满足a,b要求的即可 数据范围:x,y,z≤10^18

思路解析

看到这一道题之后,你会很容易的发现这一道题可以枚举,只需假定a和b的值,因为a和b肯定是a和b的因数,所以每一次加上z即可。就像这样:

while(1){
         if(a - b>=x and a + b > y){
              cout<< b<< " "<<a;
              break;
         }
         b = b+z;
         if(b > a){//如果b比a要大,说明这一种可能是错误的,于是a+1。
              a =a+z;
              b =z;
         }
}

但是当你自信满满的提交时,你会惊奇的发现只得了一半的分(别问我怎么知道的!)。当你认真审题后就会发现,这一道题x,y和z的数据竟然高达10^18,而a和b更是达到了罕见的5×10^18,用枚举当然会超时,如果不是这一道题数据良心,可能就只会有10~20分了。

那么怎么写正解呢？你会发现,这一道题非常奇怪,x和y似乎除了限制a和b之外什么用也没有了的,这在其它题目中似乎不太可能。但是,仔细观察就会发现,a和b的最大值是5×10^18而x和y只有10^18,比a和b的最大值整整小了5倍。这可能看上去没什么,但实际上却恰好是这一道题的切入点。条件说了a-b要大于x,且a+b大于y,那么如果a和b足够大,无论是和还是差都比x和y要大的话,那么只需满足这是z的倍数答案就水落石出了。

先从第一步说起,a和b的差和和都需要比x和y要大。要想满足这一个条件并不难,因为我们只需输出a和b的一组就行,所以当然可以输出的最大数,ab的最大值又是x和y的最大值的5倍,那么我们让a-b(或b-a)的值大于x和y就并非不可。那么才能使差更大？让一个取最小,一个取最大即可,最大有5e18,最小的话因为最大公约数是z，所以最小的数就是z。接下来需要让a满足第三个条件,可以直接最大值/z向下取整(因为可能有小数)再乘以z即可得到a最大得数字。

归根结底,这一道题得核心就是最大值/z(向下取整)×z,b就是z,推理出这些后,数据有1e18也不奇怪了