문제
페르마의 소정리 (Fermat's little theorem)의 내용은 다음과 같다.
p가 소수일 때, 임의의 정수 a>1에 대해서, ap == a (mod p)가 성립한다.
즉, a를 p제곱한 뒤, p로 나눴을 때, 나머지는 a가 되는 것이다.
하지만, p가 소수가 아닌 경우에 어떤 정수 a에 대해서 위의 식을 만족하는 경우가 있다. 이때, p를 밑이 a인 가짜소수라고 한다. (모든 a에 대해서 식을 만족하는 수를 카마이클 수라고 한다)
p와 a가 주어졌을 때, p가 밑이 a인 가짜소수인지 아닌지 알아내는 프로그램을 작성하시오.
출력
각 테스트 케이스에 대해서, p가 밑이 a인 가짜소수라면 yes를, 아니라면 no를 한 줄에 하나씩 출력한다.
예제 출력 1
no
no
yes
no
yes
yes
W3sicHJvYmxlbV9pZCI6IjQyMzMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMDBcdWM5ZGNcdWMxOGNcdWMyMTgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDM5OFx1Yjk3NFx1YjljOFx1Yzc1OCBcdWMxOGNcdWM4MTVcdWI5YWMgKEZlcm1hdCYjMzk7cyBsaXR0bGUgdGhlb3JlbSlcdWM3NTggXHViMGI0XHVjNmE5XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxwPnBcdWFjMDAgXHVjMThjXHVjMjE4XHVjNzdjIFx1YjU0YywgXHVjNzg0XHVjNzU4XHVjNzU4IFx1YzgxNVx1YzIxOCBhJmd0OzFcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBhPHN1cD5wPFwvc3VwPiA9PSBhIChtb2QgcClcdWFjMDAgXHVjMTMxXHViOWJkXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM5ODksIGFcdWI5N2MgcFx1YzgxY1x1YWNmMVx1ZDU1YyBcdWI0YTQsIHBcdWI4NWMgXHViMDk4XHViMjM0XHVjNzQ0IFx1YjU0YywgXHViMDk4XHViYTM4XHVjOWMwXHViMjk0IGFcdWFjMDAgXHViNDE4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTU4XHVjOWMwXHViOWNjLCBwXHVhYzAwIFx1YzE4Y1x1YzIxOFx1YWMwMCBcdWM1NDRcdWIyY2MgXHVhY2JkXHVjNmIwXHVjNWQwIFx1YzViNFx1YjVhNCBcdWM4MTVcdWMyMTggYVx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVjNzA0XHVjNzU4IFx1YzJkZFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViNTRjLCBwXHViOTdjIFx1YmMxMVx1Yzc3NCBhXHVjNzc4IFx1YWMwMFx1YzlkY1x1YzE4Y1x1YzIxOFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuIChcdWJhYThcdWI0ZTAgYVx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVjMmRkXHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWMyMThcdWI5N2MgXHVjZTc0XHViOWM4XHVjNzc0XHVkMDc0IFx1YzIxOFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQpPFwvcD5cclxuXHJcbjxwPnBcdWM2NDAgYVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBwXHVhYzAwIFx1YmMxMVx1Yzc3NCBhXHVjNzc4IFx1YWMwMFx1YzlkY1x1YzE4Y1x1YzIxOFx1Yzc3OFx1YzljMCBcdWM1NDRcdWIyY2NcdWM5YzAgXHVjNTRjXHVjNTQ0XHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIDxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIHBcdWM2NDAgYVx1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAmcXVvdDswIDAmcXVvdDtcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbHQ7IHAgJmxlOyAxLDAwMCwwMDAsMDAwLCAxICZsdDsgYSAmbHQ7IHApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBwXHVhYzAwIFx1YmMxMVx1Yzc3NCBhXHVjNzc4IFx1YWMwMFx1YzlkY1x1YzE4Y1x1YzIxOFx1Yjc3Y1x1YmE3NCB5ZXNcdWI5N2MsIFx1YzU0NFx1YjJjOFx1Yjc3Y1x1YmE3NCBub1x1Yjk3YyBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNDIzMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBzZXVkb3ByaW1lIG51bWJlcnMiLCJkZXNjcmlwdGlvbiI6IjxwPkZlcm1hdCYjMzk7cyB0aGVvcmVtIHN0YXRlcyB0aGF0IGZvciBhbnkgcHJpbWUgbnVtYmVyIHAgYW5kIGZvciBhbnkgaW50ZWdlciBhICZndDsgMSwgYTxzdXA+cDxcL3N1cD4gPT0gYSAobW9kIHApLiBUaGF0IGlzLCBpZiB3ZSByYWlzZSBhIHRvIHRoZSBwdGggcG93ZXIgYW5kIGRpdmlkZSBieSBwLCB0aGUgcmVtYWluZGVyIGlzIGEuIFNvbWUgKGJ1dCBub3QgdmVyeSBtYW55KSBub24tcHJpbWUgdmFsdWVzIG9mIHAsIGtub3duIGFzIGJhc2UtYSBwc2V1ZG9wcmltZXMsIGhhdmUgdGhpcyBwcm9wZXJ0eSBmb3Igc29tZSBhLiAoQW5kIHNvbWUsIGtub3duIGFzIENhcm1pY2hhZWwgTnVtYmVycywgYXJlIGJhc2UtYSBwc2V1ZG9wcmltZXMgZm9yIGFsbCBhLik8XC9wPlxyXG5cclxuPHA+R2l2ZW4gMiAmbHQ7IHAgJmxlOyAxLDAwMCwwMDAsMDAwIGFuZCAxICZsdDsgYSAmbHQ7IHAsIGRldGVybWluZSB3aGV0aGVyIG9yIG5vdCBwIGlzIGEgYmFzZS1hIHBzZXVkb3ByaW1lLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW5wdXQgY29udGFpbnMgc2V2ZXJhbCB0ZXN0IGNhc2VzIGZvbGxvd2VkIGJ5IGEgbGluZSBjb250YWluaW5nICZxdW90OzAgMCZxdW90Oy4gRWFjaCB0ZXN0IGNhc2UgY29uc2lzdHMgb2YgYSBsaW5lIGNvbnRhaW5pbmcgcCBhbmQgYS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCAmcXVvdDt5ZXMmcXVvdDsgaWYgcCBpcyBhIGJhc2UtYSBwc2V1ZG9wcmltZTsgb3RoZXJ3aXNlIG91dHB1dCAmcXVvdDtubyZxdW90Oy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d