코포 Mail.Ru Cup 2018 Round 2 - C번

http://codeforces.com/contest/1055/problem/C

어제 간단한데 안풀려서 그냥 잤다.

http://codeforces.com/contest/1055/submission/45523903

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

LL la, lb, ra, rb, ta, tb;

int main() {
	cin >> la >> ra >> ta;
	cin >> lb >> rb >> tb;
	
	LL g = __gcd(ta, tb);
	if (la < lb) {
		swap(la, lb);
		swap(ra, rb);
		swap(ta, tb);
	}
	LL da = ra - la + 1, db = rb - lb + 1;
	LL ans = 0;
	if ((la - lb) % g == 0) {
		ans = min(da, db);
	} else {
		LL d = g - (la - lb) % g;
		ans = max(ans, min(db, da - d));
		d = g - d;
		ans = max(ans, min(db - d, da));
	}
	cout << ans << endl;
}

#include<bits/stdc++.h>
using namespace std;
int a,b,c,x,y,z,g;
int main()
{
    cin>>a>>b>>c>>x>>y>>z;
    g=__gcd(c,z);
    cout<<max(min(max(b-a+1-((x-a)%g+g)%g,0),y-x+1),min(b-a+1,y-x+1-g+((x-a)%g+g)%g));
}

남의 코드를 봐도 나중에 다시 만들기 어려울 것 같아서 여기에 메모해 놓는다.

문제요약)

링크의 사진을 보면 됨.

풀이요약)

(주기 두개 gcd)는 두 주기가 한번 반복됨에 따라 한번씩 밀리는 칸의 갯수. (아마?)

이게 0이거나, (첫번째 ans 대입) 

이걸로 시작지점 la, lb가 최대한 어긋나지 않도록 맞추거나 (두번째 ans 대입)

반대쪽 기준으로 시작지점 la, lb가 최대한 어긋나지 않도록 맞추거나 (세번째 ans 대입)

하는 것 같다.