시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 103 56 52 63.415%

문제

페르마의 소정리 (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를 포함하고 있다. 입력의 마지막 줄에는 "0 0"이 주어진다. (2 < p ≤ 1,000,000,000, 1 < a < p)

출력

각 테스트 케이스에 대해서, p가 밑이 a인 가짜소수라면 yes를, 아니라면 no를 한 줄에 하나씩 출력한다.

예제 입력 1

3 2
10 3
341 2
341 3
1105 2
1105 3
0 0

예제 출력 1

no
no
yes
no
yes
yes
W3sicHJvYmxlbV9pZCI6IjQyMzMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMDBcdWM5ZGNcdWMxOGNcdWMyMTgiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1ZDM5OFx1Yjk3NFx1YjljOFx1Yzc1OCBcdWMxOGNcdWM4MTVcdWI5YWMgKEZlcm1hdCYjMzk7cyBsaXR0bGUgdGhlb3JlbSlcdWM3NTggXHViMGI0XHVjNmE5XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdHBcdWFjMDAgXHVjMThjXHVjMjE4XHVjNzdjIFx1YjU0YywgXHVjNzg0XHVjNzU4XHVjNzU4IFx1YzgxNVx1YzIxOCBhJmd0OzFcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBhPHN1cD5wPFwvc3VwPiA9PSBhIChtb2QgcClcdWFjMDAgXHVjMTMxXHViOWJkXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM5ODksIGFcdWI5N2MgcFx1YzgxY1x1YWNmMVx1ZDU1YyBcdWI0YTQsIHBcdWI4NWMgXHViMDk4XHViMjM0XHVjNzQ0IFx1YjU0YywgXHViMDk4XHViYTM4XHVjOWMwXHViMjk0IGFcdWFjMDAgXHViNDE4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVkNTU4XHVjOWMwXHViOWNjLCBwXHVhYzAwIFx1YzE4Y1x1YzIxOFx1YWMwMCBcdWM1NDRcdWIyY2MgXHVhY2JkXHVjNmIwXHVjNWQwIFx1YzViNFx1YjVhNCBcdWM4MTVcdWMyMTggYVx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVjNzA0XHVjNzU4IFx1YzJkZFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YjU0YywgcFx1Yjk3YyBcdWJjMTFcdWM3NzQgYVx1Yzc3OCBcdWFjMDBcdWM5ZGNcdWMxOGNcdWMyMThcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LiAoXHViYWE4XHViNGUwIGFcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1YzJkZFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVjMjE4XHViOTdjIFx1Y2U3NFx1YjljOFx1Yzc3NFx1ZDA3NCBcdWMyMThcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0KTxcL3A+XHJcblxyXG48cD5cclxuXHRwXHVjNjQwIGFcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgcFx1YWMwMCBcdWJjMTFcdWM3NzQgYVx1Yzc3OCBcdWFjMDBcdWM5ZGNcdWMxOGNcdWMyMThcdWM3NzhcdWM5YzAgXHVjNTQ0XHViMmNjXHVjOWMwIFx1YzU0Y1x1YzU0NFx1YjBiNFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIHBcdWM2NDAgYVx1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAmcXVvdDswIDAmcXVvdDtcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbHQ7IHAgJmxlOyAxLDAwMCwwMDAsMDAwLCAxICZsdDsgYSAmbHQ7IHApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBwXHVhYzAwIFx1YmMxMVx1Yzc3NCBhXHVjNzc4IFx1YWMwMFx1YzlkY1x1YzE4Y1x1YzIxOFx1Yjc3Y1x1YmE3NCB5ZXNcdWI5N2MsIFx1YzU0NFx1YjJjOFx1Yjc3Y1x1YmE3NCBub1x1Yjk3YyBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDIzMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBzZXVkb3ByaW1lIG51bWJlcnMiLCJkZXNjcmlwdGlvbiI6IjxwPkZlcm1hdCYjMzk7cyB0aGVvcmVtIHN0YXRlcyB0aGF0IGZvciBhbnkgcHJpbWUgbnVtYmVyIHAgYW5kIGZvciBhbnkgaW50ZWdlciBhICZndDsgMSwgYTxzdXA+cDxcL3N1cD4gPT0gYSAobW9kIHApLiBUaGF0IGlzLCBpZiB3ZSByYWlzZSBhIHRvIHRoZSBwdGggcG93ZXIgYW5kIGRpdmlkZSBieSBwLCB0aGUgcmVtYWluZGVyIGlzIGEuIFNvbWUgKGJ1dCBub3QgdmVyeSBtYW55KSBub24tcHJpbWUgdmFsdWVzIG9mIHAsIGtub3duIGFzIGJhc2UtYSBwc2V1ZG9wcmltZXMsIGhhdmUgdGhpcyBwcm9wZXJ0eSBmb3Igc29tZSBhLiAoQW5kIHNvbWUsIGtub3duIGFzIENhcm1pY2hhZWwgTnVtYmVycywgYXJlIGJhc2UtYSBwc2V1ZG9wcmltZXMgZm9yIGFsbCBhLik8XC9wPlxyXG5cclxuPHA+R2l2ZW4gMiAmbHQ7IHAgJmxlOyAxLDAwMCwwMDAsMDAwIGFuZCAxICZsdDsgYSAmbHQ7IHAsIGRldGVybWluZSB3aGV0aGVyIG9yIG5vdCBwIGlzIGEgYmFzZS1hIHBzZXVkb3ByaW1lLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW5wdXQgY29udGFpbnMgc2V2ZXJhbCB0ZXN0IGNhc2VzIGZvbGxvd2VkIGJ5IGEgbGluZSBjb250YWluaW5nICZxdW90OzAgMCZxdW90Oy4gRWFjaCB0ZXN0IGNhc2UgY29uc2lzdHMgb2YgYSBsaW5lIGNvbnRhaW5pbmcgcCBhbmQgYS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCAmcXVvdDt5ZXMmcXVvdDsgaWYgcCBpcyBhIGJhc2UtYSBwc2V1ZG9wcmltZTsgb3RoZXJ3aXNlIG91dHB1dCAmcXVvdDtubyZxdW90Oy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=