시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB155322638.806%

문제

해시(hash)란 주어진 데이터를 하나의 수로 표현하는 것을 말한다. 예를 들어서 "1024"와 같은 문자열을 1024 라는 수로 생각하는 방법은 해시의 한 예이다. 또, 영단어에서 'a'부터 'z'까지를 1에서 26까지의 수로 생각하여 그 수들을 합한 것도 해시의 한 예이다. 이런 해시를 적용하면 "ab"와 같은 영단어는 3이라는 수가 되고, "ace"와 같은 영단어는 9라는 수가 된다.

당신은 그래프에 대해서 해시 함수를 하나 설계하였다. 당신이 설계한 해시 값은 그래프의 1번 정점에서 2번 정점까지 가는 모든 경로들의 경로 값의 최소공배수로 정의한다. 경로 값은 경로 상에 있는 모든 간선의 가중치들의 최대공약수로 정의한다. 물론 경로에서는 같은 정점이 두 번 이상 나와서는 안 된다.

예를 들어 위와 같은 그래프를 보자. 위의 그래프에서 1번 정점에서 2번 정점까지 가는 경로는 1-4-2, 1-3-2의 두 개가 있다. 각 경로의 경로 값은 2(16, 6의 최대공약수), 3(3, 9의 최대공약수)이 되고, 따라서 해시 값은 6(2, 3의 최소공배수)이 된다.

하나의 그래프가 주어졌을 때, 그 그래프의 해시 값(위에서 설계한 해시 함수를 이용하여 계산한)을 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 그래프의 정점의 개수 N(2 ≤ N ≤ 30)이 주어진다. 다음 N개의 줄에는 N개의 음 아닌 정수로 대칭적인 인접 행렬이 주어진다. 0인 경우는 간선이 없을 때를 나타내며, 그 외의 간선의 가중치는 1이상 5,000이하의 자연수이다.

출력

첫째 줄에 해시 값을 출력한다. 이 값은 10진수로 1000자리를 넘지 않는다.

예제 입력 1

4
0 0 3 16
0 0 9 6
3 9 0 0
16 6 0 0

예제 출력 1

6
W3sicHJvYmxlbV9pZCI6IjIzMjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkZjhcdWI3OThcdWQ1MDRcdWM3NTggXHVkNTc0XHVjMmRjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ1NzRcdWMyZGMoaGFzaClcdWI3ODAgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1Yjk3YyBcdWQ1NThcdWIwOThcdWM3NTggXHVjMjE4XHViODVjIFx1ZDQ1Y1x1ZDYwNFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NDQgXHViOWQwXHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0XHVjMTFjICZxdW90OzEwMjQmcXVvdDtcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCAxMDI0IFx1Yjc3Y1x1YjI5NCBcdWMyMThcdWI4NWMgXHVjMGRkXHVhYzAxXHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWQ1NzRcdWMyZGNcdWM3NTggXHVkNTVjIFx1YzYwOFx1Yzc3NFx1YjJlNC4gXHViNjEwLCBcdWM2MDFcdWIyZThcdWM1YjRcdWM1ZDBcdWMxMWMgJiMzOTthJiMzOTtcdWJkODBcdWQxMzAgJiMzOTt6JiMzOTtcdWFlNGNcdWM5YzBcdWI5N2MgMVx1YzVkMFx1YzExYyAyNlx1YWU0Y1x1YzljMFx1Yzc1OCBcdWMyMThcdWI4NWMgXHVjMGRkXHVhYzAxXHVkNTU4XHVjNWVjIFx1YWRmOCBcdWMyMThcdWI0ZTRcdWM3NDQgXHVkNTY5XHVkNTVjIFx1YWM4M1x1YjNjNCBcdWQ1NzRcdWMyZGNcdWM3NTggXHVkNTVjIFx1YzYwOFx1Yzc3NFx1YjJlNC4gXHVjNzc0XHViN2YwIFx1ZDU3NFx1YzJkY1x1Yjk3YyBcdWM4MDFcdWM2YTlcdWQ1NThcdWJhNzQgJnF1b3Q7YWImcXVvdDtcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YzYwMVx1YjJlOFx1YzViNFx1YjI5NCAzXHVjNzc0XHViNzdjXHViMjk0IFx1YzIxOFx1YWMwMCBcdWI0MThcdWFjZTAsICZxdW90O2FjZSZxdW90O1x1YzY0MCBcdWFjMTlcdWM3NDAgXHVjNjAxXHViMmU4XHVjNWI0XHViMjk0IDlcdWI3N2NcdWIyOTQgXHVjMjE4XHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmY5XHVjMmUwXHVjNzQwIFx1YWRmOFx1Yjc5OFx1ZDUwNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVkNTc0XHVjMmRjIFx1ZDU2OFx1YzIxOFx1Yjk3YyBcdWQ1NThcdWIwOTggXHVjMTI0XHVhY2M0XHVkNTU4XHVjNjAwXHViMmU0LiBcdWIyZjlcdWMyZTBcdWM3NzQgXHVjMTI0XHVhY2M0XHVkNTVjIFx1ZDU3NFx1YzJkYyBcdWFjMTJcdWM3NDAgXHVhZGY4XHViNzk4XHVkNTA0XHVjNzU4IDFcdWJjODggXHVjODE1XHVjODEwXHVjNWQwXHVjMTFjIDJcdWJjODggXHVjODE1XHVjODEwXHVhZTRjXHVjOWMwIFx1YWMwMFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVhY2JkXHViODVjXHViNGU0XHVjNzU4IFx1YWNiZFx1Yjg1YyBcdWFjMTJcdWM3NTggXHVjZDVjXHVjMThjXHVhY2Y1XHViYzMwXHVjMjE4XHViODVjIFx1YzgxNVx1Yzc1OFx1ZDU1Y1x1YjJlNC4gXHVhY2JkXHViODVjIFx1YWMxMlx1Yzc0MCBcdWFjYmRcdWI4NWMgXHVjMGMxXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVhYzA0XHVjMTIwXHVjNzU4IFx1YWMwMFx1YzkxMVx1Y2U1OFx1YjRlNFx1Yzc1OCBcdWNkNWNcdWIzMDBcdWFjZjVcdWM1N2RcdWMyMThcdWI4NWMgXHVjODE1XHVjNzU4XHVkNTVjXHViMmU0LiBcdWJiM2NcdWI4NjAgXHVhY2JkXHViODVjXHVjNWQwXHVjMTFjXHViMjk0IFx1YWMxOVx1Yzc0MCBcdWM4MTVcdWM4MTBcdWM3NzQgXHViNDUwIFx1YmM4OCBcdWM3NzRcdWMwYzEgXHViMDk4XHVjNjQwXHVjMTFjXHViMjk0IFx1YzU0OCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgaGVpZ2h0PVwiMjM5XCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDEwMTFcL2hhLlBOR1wiIHdpZHRoPVwiMjY4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgXHVjNzA0XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWFkZjhcdWI3OThcdWQ1MDRcdWI5N2MgXHViY2Y0XHVjNzkwLiBcdWM3MDRcdWM3NTggXHVhZGY4XHViNzk4XHVkNTA0XHVjNWQwXHVjMTFjIDFcdWJjODggXHVjODE1XHVjODEwXHVjNWQwXHVjMTFjIDJcdWJjODggXHVjODE1XHVjODEwXHVhZTRjXHVjOWMwIFx1YWMwMFx1YjI5NCBcdWFjYmRcdWI4NWNcdWIyOTQgMS00LTIsIDEtMy0yXHVjNzU4IFx1YjQ1MCBcdWFjMWNcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVhY2JkXHViODVjXHVjNzU4IFx1YWNiZFx1Yjg1YyBcdWFjMTJcdWM3NDAgMigxNiwgNlx1Yzc1OCBcdWNkNWNcdWIzMDBcdWFjZjVcdWM1N2RcdWMyMTgpLCAzKDMsIDlcdWM3NTggXHVjZDVjXHViMzAwXHVhY2Y1XHVjNTdkXHVjMjE4KVx1Yzc3NCBcdWI0MThcdWFjZTAsIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWQ1NzRcdWMyZGMgXHVhYzEyXHVjNzQwIDYoMiwgM1x1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjZjVcdWJjMzBcdWMyMTgpXHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTU4XHViMDk4XHVjNzU4IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFkZjggXHVhZGY4XHViNzk4XHVkNTA0XHVjNzU4IFx1ZDU3NFx1YzJkYyBcdWFjMTIoXHVjNzA0XHVjNWQwXHVjMTFjIFx1YzEyNFx1YWNjNFx1ZDU1YyBcdWQ1NzRcdWMyZGMgXHVkNTY4XHVjMjE4XHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU1OFx1YzVlYyBcdWFjYzRcdWMwYjBcdWQ1NWMpXHVjNzQ0IFx1YWQ2Y1x1ZDU3NFx1YjBiNFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFkZjhcdWI3OThcdWQ1MDRcdWM3NTggXHVjODE1XHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOCBOKDIgJmxlOyBOICZsZTsgMzApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IE5cdWFjMWNcdWM3NTggXHVjNzRjIFx1YzU0NFx1YjJjYyBcdWM4MTVcdWMyMThcdWI4NWMgXHViMzAwXHVjZTZkXHVjODAxXHVjNzc4IFx1Yzc3OFx1YzgxMSBcdWQ1ODlcdWI4MmNcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAwXHVjNzc4IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWFjMDRcdWMxMjBcdWM3NzQgXHVjNWM2XHVjNzQ0IFx1YjU0Y1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWJhNzAsIFx1YWRmOCBcdWM2NzhcdWM3NTggXHVhYzA0XHVjMTIwXHVjNzU4IFx1YWMwMFx1YzkxMVx1Y2U1OFx1YjI5NCAxXHVjNzc0XHVjMGMxIDUsMDAwXHVjNzc0XHVkNTU4XHVjNzU4IFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDU3NFx1YzJkYyBcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM3NzQgXHVhYzEyXHVjNzQwIDEwXHVjOWM0XHVjMjE4XHViODVjIDEwMDBcdWM3OTBcdWI5YWNcdWI5N2MgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyMzI4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ293IE1hdGgiLCJkZXNjcmlwdGlvbiI6IjxwPlRha2luZyB0aGVpciBjdWUgZnJvbSB0aGUgYnVpbGRlcnMgb2YgdGhlIFVTQSYjMzk7cyBJbnRlcnN0YXRlIEhpZ2h3YXkgc3lzdGVtLCB0aGUgY293cyBoYXZlIGludHJvZHVjZWQgdGhlIEludGVycGFzdHVyZSBQYXRoIG51bWJlcmluZyBzeXN0ZW0uIFRoZXkgaGF2ZSBhbHJlYWR5IG51bWJlcmVkIHRoZSBOICgyICZsdDs9IE4gJmx0Oz0gMzApIHBhc3R1cmVzIHdpdGggdGhlIGludGVnZXJzIDEuLk4gYW5kIG5vdyBhcmUgbnVtYmVyaW5nIGVhY2ggcGF0aCBiZXR3ZWVuIHR3byBwYXN0dXJlcyB3aXRoIGl0cyBvd24gZGlzdGluY3QgSW50ZXJwYXN0dXJlIFBhdGggbnVtYmVyIGluIHRoZSByYW5nZSAxLi41MDAwICZuYnNwOyhlLmcuLCBJLTkgYW5kIEktMTYpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5JbiBhbiBleGFtcGxlIEludGVycGFzdHVyZSBQYXRoIG1hcCwgZm91ciBwYXN0dXJlcyBudW1iZXJlZCAxLCAyLCAzLCBhbmQgNCBhcmUgY29ubmVjdGVkIGJ5IEludGVycGFzdHVyZSBQYXRocyBJLTMsIEktNiwgSS05LCBhbmQgSS0xNjombmJzcDs8XC9wPlxyXG5cclxuPHByZT5cclxuICAgICAgICAgICAgICAgICAgNC0tJmx0OyBJLTYmZ3Q7LS0yXHJcbiAgICAgICAgICAgICAgICAgXC8gICAgICAgICBcL1xyXG4gICAgICAgICAgICAgJmx0OyBJLTE2Jmd0OyAgICAgJmx0OyBJLTkmZ3Q7ICAgXHJcbiAgICAgICAgICAgICAgIFwvICAgICAgICAgXC9cclxuICAgICAgICAgICAgICAxLS0mbHQ7IEktMyZndDstLTMgIFxyXG48XC9wcmU+XHJcblxyXG48cD5CZXNzaWUgbGlrZXMgdG8gd2FsayBmcm9tIHBhc3R1cmUgMSB0byBwYXN0dXJlIDIgb24gdGhlIG5pZnR5IG5ldyBJbnRlcnBhc3R1cmUgc3lzdGVtLiBEdXJpbmcgZWFjaCB3YWxrLCBzaGUgbmV2ZXIgdmlzaXRzIHRoZSBzYW1lIHBhc3R1cmUgdHdpY2UsIHNvIHBvc3NpYmxlIHdhbGtzIG9uIHRoZSBzYW1wbGUgbWFwIGFib3ZlIGFyZSAxLTQtMiBhbmQgMS0zLTIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk92ZXIgdGhlIHllYXJzLCBCZXNzaWUgaGFzIGRldmVsb3BlZCBhbiBhbWF6aW5nIG1hdGhlbWF0aWNhbCBza2lsbCB0aGF0IHNoZSBsaWtlcyB0byBleGVyY2lzZS4gRHVyaW5nIGVhY2ggd2Fsaywgc2hlIGVuam95cyBmaW5kaW5nIHRoZSBncmVhdGVzdCBjb21tb24gZmFjdG9yIChHQ0YpIG9mIHRoZSBJbnRlcnBhc3R1cmUgUGF0aHMgdGhhdCBzaGUgdHJhdmVyc2VzLiBGb3IgaW5zdGFuY2UsIHRoZSB3YWxrIGRlc2lnbmF0ZWQgMS00LTIgdG91Y2hlcyBJLTE2IGFuZCBJLTYgd2hpY2ggaGF2ZSB0aGUgZ3JlYXRlc3QgY29tbW9uIGZhY3RvciBvZiAyIChzaW5jZSAyIHByb3Blcmx5IGRpdmlkZXMgaW50byAxNiBhbmQgNiBidXQgbm8gbGFyZ2VyIGludGVnZXIgZG9lcykuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFzIHNoZSB3YWxrcyB0aGUgcGFzdHVyZXMgZGF5IGFmdGVyIGRheSwgc2hlIHRha2VzIGFsbCB0aGUgcG9zc2libGUgcm91dGVzIGZyb20gcGFzdHVyZSAxIHRvIHBhc3R1cmUgMiBhbmQgcmVtZW1iZXJzIGVhY2ggb2YgdGhlIEdDRnMuIEFmdGVyIHNoZSBoYXMgdGFrZW4gZXZlcnkgcG9zc2libGUgd2FsayBvbmNlLCBzaGUgY29tcHV0ZXMgdGhlIGxlYXN0IGNvbW1vbiBtdWx0aXBsZSAoTENNKSBvZiBhbGwgdGhlIEdDRnMuIEZvciB0aGlzIGV4YW1wbGUsIHRoZSB0d28gR0NGIHZhbHVlcyBhcmUgMiBhbmQgMyAoR0NGKDYsMTYpPTIgYW5kIEdDRigzLDkpPTMpLCBzbyB0aGUgTENNIGlzIDYuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciBsYXJnZSBuZXR3b3JrcyBvZiBwYXRocywgQmVzc2llIG1pZ2h0IGdldCB0aXJlZCBvZiBhbGwgdGhlIHdhbGtpbmcsIGJ1dCBzaGUgcmVhbGx5IHdhbnRzIHRvIGtub3cgdGhlIExDTSBmb3IgZXZlcnkgbWFwLiBDYWxjdWxhdGUgdGhhdCBudW1iZXIgZm9yIGhlci4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBOJm5ic3A7PFwvbGk+XHJcblx0PGxpPkxpbmVzIDIuLk4rMTogVGhlc2UgTiBsaW5lcyByZXByZXNlbnQgdGhlIHN5bW1ldHJpYyBJbnRlcnBhc3R1cmUgUGF0aCBjb25uZWN0aXZpdHkgbWF0cml4IG9mIHRoZSBwYXN0dXJlcy4gTGluZSBMIHNob3dzIHRoZSBjb25uZWN0aXZpdHkgYmV0d2VlbiBwYXN0dXJlIEwtMSBhbmQgdGhlIG90aGVyIHBhc3R1cmVzIHdpdGggaXRzIE4gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzLiBUaGUgZmlyc3QgaW50ZWdlciBvbiBlYWNoIGxpbmUgaXMgdGhlIEludGVycGFzdHVyZSBQYXRoIG51bWJlciB0aGF0IGNvbm5lY3RzIHBhc3R1cmUgTC0xIGFuZCBhbmQgcGFzdHVyZSAxOyB0aGUgc2Vjb25kIGludGVnZXIgaXMgdGhlIElQIG51bWJlciBjb25uZWN0aW5nIHBhc3R1cmUgTC0xIGFuZCBwYXN0dXJlIDI7IGV0Yy4gSWYgcGFzdHVyZSBBIGNvbm5lY3RzIHRvIHBhc3R1cmUgQiwgdGhlbiBwYXN0dXJlIEIgY29ubmVjdHMgdG8gUGFzdHVyZSBBLiBXaGVuIG5vIEludGVycGFzdHVyZSBQYXRoIGlzIGF2YWlsYWJsZSwgdGhlIGludGVnZXIgaXMgMC48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPkEgc2luZ2xlIGxpbmUgd2l0aCBhIHNpbmdsZSBpbnRlZ2VyIHRoYXQgaXMgdGhlIExDTSBvZiB0aGUgR0NGcyBvZiBhbGwgdGhlIHBvc3NpYmxlIHdhbGtzIGZyb20gcGFzdHVyZSAxIHRvIHBhc3R1cmUgMi4gSXQgaXMgZ3VhcmFudGVlZCB0aGF0IHRoZSBhbnN3ZXIgd2lsbCBjb250YWluIDEwMDAmbmJzcDtvciBmZXdlciBkaWdpdHMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > USA Computing Olympiad > 2002-2003 Season > USACO February 2003 Contest > Green 1번

  • 문제의 오타를 찾은 사람: klimmek55