시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB68024416736.304%

문제

상근이는 데이터베이스 수업 시간에 교수님 몰래 교실을 나갔다. 결국 교수님에게 불려가게 되었고, 교수님은 다음과 같은 수학 숙제를 내주었다.

정수 N개가 주어진다. 이때, 친구의 개수를 구하라.

상근이는 이 문제를 받고 친구가 무엇인지 궁금해졌다. 데이터베이스 조교 동규는 두 수를 이루는 숫자가 적어도 하나 겹치는 쌍을 친구라고 한다고 했다. (겹치는 위치는 달라도 된다)

상근이의 숙제를 하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

다음 N개 줄에는 [1, 1018] 범위 안에 있는 양의 정수가 주어진다. 이 수가 교수님이 상근이에게 숙제로 전달한 수이다. 같은 수가 두 번 이상 주어지지 않는다.

출력

첫째 줄에 친구의 개수를 출력한다.

예제 입력 1

3
4
20
44

예제 출력 1

1

예제 입력 2

4
32
51
123
282

예제 출력 2

4
W3sicHJvYmxlbV9pZCI6IjI4MjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMThcdWM1YzVcdWMyZGNcdWFjMDRcdWM1ZDAgXHVhZDUwXHVjMjE4XHViMmQ4IFx1YmFiMFx1Yjc5OCBcdWFkNTBcdWMyZTRcdWM3NDQgXHViMDk4XHVhYzA0IFx1YzBjMVx1YWRmY1x1Yzc3NCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1YmNhMFx1Yzc3NFx1YzJhNCBcdWMyMThcdWM1YzUgXHVjMmRjXHVhYzA0XHVjNWQwIFx1YWQ1MFx1YzIxOFx1YjJkOCBcdWJhYjBcdWI3OTggXHVhZDUwXHVjMmU0XHVjNzQ0IFx1YjA5OFx1YWMxNFx1YjJlNC4gXHVhY2IwXHVhZDZkIFx1YWQ1MFx1YzIxOFx1YjJkOFx1YzVkMFx1YWM4YyBcdWJkODhcdWI4MjRcdWFjMDBcdWFjOGMgXHViNDE4XHVjNWM4XHVhY2UwLCBcdWFkNTBcdWMyMThcdWIyZDhcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWMyMThcdWQ1NTkgXHVjMjE5XHVjODFjXHViOTdjIFx1YjBiNFx1YzhmY1x1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODE1XHVjMjE4IE5cdWFjMWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1Y2U1Y1x1YWQ2Y1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViNzdjLjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNzc0IFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWJjMWJcdWFjZTAgXHVjZTVjXHVhZDZjXHVhYzAwJm5ic3A7XHViYjM0XHVjNWM3XHVjNzc4XHVjOWMwIFx1YWQ4MVx1YWUwOFx1ZDU3NFx1Yzg0Y1x1YjJlNC4gXHViMzcwXHVjNzc0XHVkMTMwXHViY2EwXHVjNzc0XHVjMmE0IFx1Yzg3MFx1YWQ1MCBcdWIzZDlcdWFkZGNcdWIyOTQgXHViNDUwIFx1YzIxOFx1Yjk3YyBcdWM3NzRcdWI4ZThcdWIyOTQgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YzgwMVx1YzViNFx1YjNjNCBcdWQ1NThcdWIwOTggXHVhY2I5XHVjZTU4XHViMjk0IFx1YzMwZFx1Yzc0NCBcdWNlNWNcdWFkNmNcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0XHVhY2UwIFx1ZDU4OFx1YjJlNC4gKFx1YWNiOVx1Y2U1OFx1YjI5NCBcdWM3MDRcdWNlNThcdWIyOTQgXHViMmVjXHViNzdjXHViM2M0IFx1YjQxY1x1YjJlNCk8XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1YzIxOVx1YzgxY1x1Yjk3YyBcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMjE4XHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMSwwMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgWzEsIDEwPHN1cD4xODxcL3N1cD5dIFx1YmM5NFx1YzcwNCBcdWM1NDhcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHVjMjE4XHVhYzAwIFx1YWQ1MFx1YzIxOFx1YjJkOFx1Yzc3NCBcdWMwYzFcdWFkZmNcdWM3NzRcdWM1ZDBcdWFjOGMgXHVjMjE5XHVjODFjXHViODVjIFx1YzgwNFx1YjJlY1x1ZDU1YyBcdWMyMThcdWM3NzRcdWIyZTQuIFx1YWMxOVx1Yzc0MCBcdWMyMThcdWFjMDAgXHViNDUwIFx1YmM4OCBcdWM3NzRcdWMwYzEgXHVjOGZjXHVjNWI0XHVjOWMwXHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2U1Y1x1YWQ2Y1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI4MjUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJLT01QSVx1MDEwNkkiLCJkZXNjcmlwdGlvbiI6IjxwPkFmdGVyIHN1Y2Nlc3NmdWxseSBzb2x2aW5nIGhpcyBtYXRoIGhvbWV3b3JrIGZyb20gdGhlIHByZXZpb3VzIHRhc2ssIE1pcmtvIGhhcyBiZWNvbWUgYm9yZWQsIHNvIGhlIGhhcyBtYWRlIGEgbGlzdCBvZiBOIGxhcmdlIGludGVnZXJzLiBPbiB0aGUgbGlzdCB0aGVyZSBhcmUgc29tZSBwYWlycyBvZiBudW1iZXJzIHRoYXQgaGUgbGlrZXMsIGFuZCBzb21lIHBhaXJzIGhlIGRvZXNuJnJzcXVvO3QgbGlrZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TWlya28gaGFzIG5hbWVkIHRoZSBwYWlycyB0aGF0IGhlIGxpa2VzIHBhbHMuIFR3byBudW1iZXJzIGFyZSBwYWxzIGlmIHRoZXkgaGF2ZSBhdCBsZWFzdCBvbmUgZGlnaXQgaW4gY29tbW9uIChub3QgbmVjZXNzYXJpbHkgaW4gdGhlIHNhbWUgcG9zaXRpb24pLiZuYnNwOzxcL3A+XHJcblxyXG48cD5IZWxwIE1pcmtvIGNvdW50IGhvdyBtYW55IHBhaXJzIG9mIG51bWJlcnMgaW4gaGlzIGxpc3QgYXJlIHBhbHMuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgcG9zaXRpdmUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDEgMDAwIDAwMCkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIG5leHQgTiBsaW5lcyBjb250YWlucyBhIHBvc2l0aXZlIGludGVnZXIgZnJvbSB0aGUgcmFuZ2UgWzEsIDEwPHN1cD4xODxcL3N1cD5dLCBhIG51bWJlciBmcm9tIE1pcmtvJnJzcXVvO3MgbGlzdC4gTm8gdHdvIG51bWJlcnMgaW4gdGhlIGxpc3Qgd2lsbCBiZSBlcXVhbC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSBudW1iZXIgb2YgcGFpcnMgdGhhdCBhcmUgcGFscy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2011/2012 > Contest #2 4번