시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB149691885362.082%

문제

무엇이든 덮어버리는 것을 좋아하는 지은이는 한변의 길이가 A인 정삼각형을 한변의 길이가 B인 정삼각형으로 완전히 덮어 버리고자 한다. 

두개의 정수 A, B 가 주어지고, B ≤ A 이고, A를 B로 나눌수 있을때, 한 변의 길이가 A인 정삼각형을 완전하게 덮기 위한, 한변의 길이가 B인 정삼각형의 개수를 구하라.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. (T ≤ 1000)

각각의 테스트 케이스는 한줄로 이루어져 있으며 두개의 정수 A, B 가 (1 ≤ B ≤ A ≤ 1,000,000, B|A) 주어진다.

출력

각 테스트 케이스마다 한변의 길이가 A인 정삼각형을 완벽하게 덮을 수 있는 한변의 길이가 B인 정삼각형의 최소 개수를 출력한다.

예제 입력 1

2
2 1
3 3

예제 출력 1

4
1
W3sicHJvYmxlbV9pZCI6IjExMzEyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMGJjXHVhYzAxIFx1YmIzNFx1YjJhYyAtIDIiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YmIzNFx1YzVjN1x1Yzc3NFx1YjRlMCBcdWIzNmVcdWM1YjRcdWJjODRcdWI5YWNcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YjI5NCBcdWM5YzBcdWM3NDBcdWM3NzRcdWIyOTQgXHVkNTVjXHViY2MwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCBBXHVjNzc4IFx1YzgxNVx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWQ1NWNcdWJjYzBcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIEJcdWM3NzggXHVjODE1XHVjMGJjXHVhYzAxXHVkNjE1XHVjNzNjXHViODVjIFx1YzY0NFx1YzgwNFx1ZDc4OCBcdWIzNmVcdWM1YjQgXHViYzg0XHViOWFjXHVhY2UwXHVjNzkwIFx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHViNDUwXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBBLCBCIFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsJm5ic3A7QiAmbGU7IEEgXHVjNzc0XHVhY2UwLCBBXHViOTdjIEJcdWI4NWMgXHViMDk4XHViMjBjXHVjMjE4IFx1Yzc4OFx1Yzc0NFx1YjU0YywgXHVkNTVjIFx1YmNjMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAgQVx1Yzc3OCBcdWM4MTVcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVjNjQ0XHVjODA0XHVkNTU4XHVhYzhjIFx1YjM2ZVx1YWUzMCBcdWM3MDRcdWQ1NWMsIFx1ZDU1Y1x1YmNjMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAmbmJzcDtCXHVjNzc4IFx1YzgxNVx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc1OCZuYnNwO1x1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoVCZuYnNwOyZsZTsgMTAwMCk8XC9wPlxyXG5cclxuPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAgXHViNDUwXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBBLCBCIFx1YWMwMCAoMSAmbGU7IEIgJmxlOyBBICZsZTsgMSwwMDAsMDAwLCBCfEEpJm5ic3A7XHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1ZDU1Y1x1YmNjMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAgQVx1Yzc3OCBcdWM4MTVcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVjNjQ0XHViY2JkXHVkNTU4XHVhYzhjIFx1YjM2ZVx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0Jm5ic3A7XHVkNTVjXHViY2MwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCZuYnNwO0JcdWM3NzgmbmJzcDtcdWM4MTVcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NTggXHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTEzMTIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUcmlhbmd1bGF0ZSBUaGlzISIsImRlc2NyaXB0aW9uIjoiPHA+R2l2ZW4gdHdvIHBvc2l0aXZlIGludGVnZXJzIEEgYW5kIEIsIHdoZXJlIEIgJmxlOyBBIGFuZCBCIGRpdmlkZXMgQSwgaG93IG1hbnkgZXF1aWxhdGVyYWwgdHJpYW5nbGVzIG9mIHNpZGUgQiB5b3UgbmVlZCB0byBjb21wbGV0ZWx5IGNvdmVyIHRoZSB0cmlhbmdsZSBvZiBzaWRlIEEuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgdGVzdCBmaWxlIHN0YXJ0cyB3aXRoIGFuIGludGVnZXIgVChUICZsZTsgMTAwMCksIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2UgY29uc2lzdHMgb2YgdHdvIGludGVnZXJzIEEgYW5kIEIgb24gYSBsaW5lLiAoMSAmbGU7IEIgJmxlOyBBICZsZTsgMSwgMDAwLCAwMDAsIEJ8QSk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCB0aGUgbWluaW11bSBudW1iZXIgb2YgZXF1aWxhdGVyYWwgdHJpYW5nbGVzIHdpdGggc2lkZSBCIHRoYXQgY2FuIGNvbXBsZXRlbHkgY292ZXIgdGhlIGVxdWlsYXRlcmFsIHRyaWFuZ2xlIHdpdGggc2lkZSBBLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Contest > Calgary Collegiate Programming Contest > CCPC 2015 Division 1 A번