NOI题库-小学奥赛QwQ

时间:2023-07-28 10:02:32
今天Loli教育我们让我们来看看NOI题库的奥赛部分,不过,为何是小学的( ⊙ o ⊙ )啊!感觉智商被各种侮辱。

余数相同问题:

描述

已知三个正整数 a,b,c。

现有一个大于1的整数x,将其作为除数分别除a,b,c,得到的余数相同。

请问满足上述条件的x的最小值是多少?

数据保证x有解。

输入

一行,三个不大于1000000的正整数a,b,c,两个整数之间用一个空格隔开。

输出

一个整数,即满足条件的x的最小值。

样例输入

300 262 205

样例输出

19

MD,这么小的范围,妹举不就好了,哪里不会了??

**现在看下数学解法:

设答案为x

A=a1x+q

B=a2x+q

C=a3x+q

然后把它们相减…

A-B=(a1-a2)*x

B-C=(a2-a3)*x

C-A=(a3-a1)*x

求这三个数的最大公约数,然后求最大公约数的最小质因子就可了…

怎么求最小质因子?…好像还是要枚举啊…

但是这样看来如果最大公约数如果等于1,就是NO ANSWER,但是题目还没有这个?….

随便一个样例卡死:

5 7 10**

噗!!