2016-2017 CT S03E08: Codeforces Trainings Season 3 Episode 8 K1 gcd

3350 단어 수론
FairWarning
On our planet, Jamcode IX, threeGreat Events occurred. They happened 26000, 11000 and 6000 slarboseconds ago.In 4000 slarboseconds, the amount of time since all of those events will bemultiples of 5000 slarboseconds, the largest possible amount...and theapocalypse will come.
Luckily for you, you live onJamcode X! The apocalypse came on Jamcode IX less than a year ago. But JamcodeX has a worrying prophecy: After the moment of reckoning, on the rst optimumanniversary of the n Great Events,the apocalypse will come. 64 bits will not save you. You have been warned.
The people of Jamcode X are veryconcerned by this prophecy. All of the Great Events have already happened, andtheir times have been measured to the nearest slarbosecond; but nobody knowswhen their optimum anniversary will occur. After studying the diary of ascientist from Jamcode IX, scientists working on the problem have come up witha theory:
The moment of reckoning is now, themoment you solve this problem. At some time y≥ 0 slarboseconds from now, the number of slarboseconds since each of theGreat Events will be divisible by some maximum number t. If you can nd the smallest value of y that gives this largest possible t, that will give you the optimum anniversary when the apocalypsewill come.
On Jamcode IX, for example, therewere 3 Great Events and they happened 26000, 11000 and 6000 slarbosecondsbefore the moment of reckoning. 4000 slarboseconds later, the amount of timesince each event was a multiple of t =5000 slarboseconds, and the apocalypse came.
Your job is to compute the amountof time until the apocalypse comes.
Input
The rst line of the input gives asingle integer n (2 ≤ n ≤ 3).
The second line of the input gives n space-separated integers ti (1 ≤ ti ≤ 108), the number of slarboseconds sinceGreat Event i occurred. It isguaranteed that ti ≠ tj for some i, j.
Output
Output one line containing theminimum number of slarboseconds until ti+y is a multiple of thelargest possible integer factor t forall i.
Examples
standard input
standard output
3 26000000 11000000 6000000
4000000
3 1 10 11
0
2 8000001 9000001
999999
Notes
Epilogue
Fortunately for the peoples of theJamcode system, the apocalypse turned out to be a mistranslation of the giantparty. Nobody from Jamcode IX bothered to pass this along, because they werehaving so much fun.
제목: 2개나 3개의 수를 주고 s를 찾아서 gcd가 가장 크도록 하세요.
문제 풀이:
시계를 채웠다
이런 법칙이 있더라고요.
n개수 +s
먼저 순서를 정하고 gcd(a[2]-a[1], a[3]-a[2],..., a[n]-a[n-1])가 그들의 최대 공약수다.
그러니까 일단 폭력을 찾아서 밟으면 돼요.
하드 버전에 대해서 큰 2점으로 찾아보시면 돼요.
ps: 최적화하려면 a[1]보다 큰 첫 번째 수를 2분에 찾아내고 이 수는 gcd의 배수로 이 수와 a[1]의 차이를 출력하면 된다.
#include
#include
#include
#include
using namespace std;
typedef long long ll;
int main(){
	ll i,a[4],n;
	scanf("%lld",&n);
	for(i=1;i<=n;i++)scanf("%lld",&a[i]);
	sort(a+1,a+1+n);
	if(n==2){
		ll now=a[2]-a[1];
		for(i=0;;i++){
			if((a[1]+i)%now==0)break;
		}
		printf("%lld
",i); } else{ ll now=__gcd(a[2]-a[1],a[3]-a[2]); for(i=0;;i++){ if((a[1]+i)%now==0)break; } printf("%lld
",i); } return 0; }

좋은 웹페이지 즐겨찾기