시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 116 66 62 65.263%

문제

페르마의 소정리 (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+XHJcblx0XHVkNTU4XHVjOWMwXHViOWNjLCBwXHVhYzAwIFx1YzE4Y1x1YzIxOFx1YWMwMCBcdWM1NDRcdWIyY2MgXHVhY2JkXHVjNmIwXHVjNWQwIFx1YzViNFx1YjVhNCBcdWM4MTVcdWMyMTggYVx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVjNzA0XHVjNzU4IFx1YzJkZFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViNTRjLCBwXHViOTdjIFx1YmMxMVx1Yzc3NCBhXHVjNzc4IFx1YWMwMFx1YzlkY1x1YzE4Y1x1YzIxOFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuIChcdWJhYThcdWI0ZTAgYVx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVjMmRkXHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWMyMThcdWI5N2MgXHVjZTc0XHViOWM4XHVjNzc0XHVkMDc0IFx1YzIxOFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQpPFwvcD5cclxuXHJcbjxwPlxyXG5cdHBcdWM2NDAgYVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBwXHVhYzAwIFx1YmMxMVx1Yzc3NCBhXHVjNzc4IFx1YWMwMFx1YzlkY1x1YzE4Y1x1YzIxOFx1Yzc3OFx1YzljMCBcdWM1NDRcdWIyY2NcdWM5YzAgXHVjNTRjXHVjNTQ0XHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgcFx1YzY0MCBhXHViOTdjIFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0ICZxdW90OzAgMCZxdW90O1x1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsdDsgcCAmbGU7IDEsMDAwLDAwMCwwMDAsIDEgJmx0OyBhICZsdDsgcCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIHBcdWFjMDAgXHViYzExXHVjNzc0IGFcdWM3NzggXHVhYzAwXHVjOWRjXHVjMThjXHVjMjE4XHViNzdjXHViYTc0IHllc1x1Yjk3YywgXHVjNTQ0XHViMmM4XHViNzdjXHViYTc0IG5vXHViOTdjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0MjMzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUHNldWRvcHJpbWUgbnVtYmVycyIsImRlc2NyaXB0aW9uIjoiPHA+RmVybWF0JiMzOTtzIHRoZW9yZW0gc3RhdGVzIHRoYXQgZm9yIGFueSBwcmltZSBudW1iZXIgcCBhbmQgZm9yIGFueSBpbnRlZ2VyIGEgJmd0OyAxLCBhPHN1cD5wPFwvc3VwPiA9PSBhIChtb2QgcCkuIFRoYXQgaXMsIGlmIHdlIHJhaXNlIGEgdG8gdGhlIHB0aCBwb3dlciBhbmQgZGl2aWRlIGJ5IHAsIHRoZSByZW1haW5kZXIgaXMgYS4gU29tZSAoYnV0IG5vdCB2ZXJ5IG1hbnkpIG5vbi1wcmltZSB2YWx1ZXMgb2YgcCwga25vd24gYXMgYmFzZS1hIHBzZXVkb3ByaW1lcywgaGF2ZSB0aGlzIHByb3BlcnR5IGZvciBzb21lIGEuIChBbmQgc29tZSwga25vd24gYXMgQ2FybWljaGFlbCBOdW1iZXJzLCBhcmUgYmFzZS1hIHBzZXVkb3ByaW1lcyBmb3IgYWxsIGEuKTxcL3A+XHJcblxyXG48cD5HaXZlbiAyICZsdDsgcCAmbGU7IDEsMDAwLDAwMCwwMDAgYW5kIDEgJmx0OyBhICZsdDsgcCwgZGV0ZXJtaW5lIHdoZXRoZXIgb3Igbm90IHAgaXMgYSBiYXNlLWEgcHNldWRvcHJpbWUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbnB1dCBjb250YWlucyBzZXZlcmFsIHRlc3QgY2FzZXMgZm9sbG93ZWQgYnkgYSBsaW5lIGNvbnRhaW5pbmcgJnF1b3Q7MCAwJnF1b3Q7LiBFYWNoIHRlc3QgY2FzZSBjb25zaXN0cyBvZiBhIGxpbmUgY29udGFpbmluZyBwIGFuZCBhLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0ICZxdW90O3llcyZxdW90OyBpZiBwIGlzIGEgYmFzZS1hIHBzZXVkb3ByaW1lOyBvdGhlcndpc2Ugb3V0cHV0ICZxdW90O25vJnF1b3Q7LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==