E D R , A S I H C RSS
ZeroWiki

Carmichael Numbers

์›๋ฌธ๋ณด๊ธฐ
----
์ธ๊ธฐ๋„:B(A,B,C), ์„ฑ๊ณต๋ฅ :๋ณดํ†ต(๋‚ฎ์Œ,๋ณดํ†ต,๋†’์Œ), ๋ ˆ๋ฒจ:2(1~4)

About CarmichaelNumbers

์•”ํ˜ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ค‘์—๋Š” ํฐ ์†Œ์ˆ˜๋ฅผ ํ™œ์šฉํ•˜๋Š” ๊ฒƒ๋„ ์žˆ๋‹ค. ํ•˜์ง€๋งŒ ์–ด๋–ค ํฐ ์ˆ˜๊ฐ€ ์†Œ์ˆ˜์ธ์ง€๋ฅผ ํŒ๋‹จํ•˜๋Š” ๊ฒƒ์€ ๊ทธ๋ฆฌ ์‰ฝ์ง€ ์•Š๋‹ค.
ํŽ˜๋ฅด๋งˆ ํ…Œ์ŠคํŠธ์™€ ๊ฐ™์ด ๋น ๋ฅธ ์†๋„๋กœ ๋งค์šฐ ์ •ํ™•ํ•˜๊ฒŒ ์†Œ์ˆ˜ ์—ฌ๋ถ€๋ฅผ ํŒ๋‹จํ•  ์ˆ˜ ์žˆ๋Š” ํ™•๋ฅ ์  ์†Œ์ˆ˜ ํ…Œ์ŠคํŠธ ๋ฐฉ๋ฒ•์ด๋ผ๋Š” ๊ฒƒ์ด ์žˆ๋‹ค. ์†Œ์ˆ˜ ์—ฌ๋ถ€๋ฅผ ํŒ๋‹จํ•ด์•ผ ํ•  ์ •์ˆ˜ n์ด ์ฃผ์–ด์กŒ์„ ๋•Œ a๋Š” 2์ด์ƒ n-1์ดํ•˜์˜ ๋‚œ์ˆ˜๋ผ๊ณ  ํ•˜์ž. ๊ทธ๋Ÿฌ๋ฉด ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์‹์ด ์„ฑ๋ฆฝํ•˜๋ฉด n์€ ์†Œ์ˆ˜์ผ ๊ฐ€๋Šฅ์„ฑ์ด ์žˆ๋‹ค.

a^n mod n = a

์–ด๋–ค ์ •์ˆ˜๊ฐ€ ์ด๋Ÿฌํ•œ ํŽ˜๋ฅด๋งˆ ํ…Œ์ŠคํŠธ๋ฅผ ์—ฌ๋Ÿฌ ๋ฒˆ ํ†ต๊ณผํ•˜๋ฉด ๊ทธ ์ •์ˆ˜๋Š” ์†Œ์ˆ˜์ผ ๊ฐ€๋Šฅ์„ฑ์ด ๋†’๋‹ค๊ณ  ํ•  ์ˆ˜ ์žˆ๋‹ค. ํ•˜์ง€๋งŒ ์•ˆ ์ข‹์€ ์†Œ์‹๋„ ์žˆ๋‹ค. ํ•ฉ์„ฑ์ˆ˜(์†Œ์ˆ˜๊ฐ€ ์•„๋‹Œ ์ˆ˜) ์ค‘์—๋Š” ๊ทธ ์ˆ˜๋ณด๋‹ค ์ž‘์€ ๋ชจ๋“  ์ •์ˆ˜์— ๋Œ€ํ•ด ์ด ํŽ˜๋ฅด๋งˆ ํ…Œ์ŠคํŠธ๋ฅผ ํ†ต๊ณผํ•˜๋Š” ๊ฒƒ๋„ ์žˆ๋‹ค. ์ด๋Ÿฐ ์ˆ˜๋ฅผ ์นด๋งˆ์ดํด ์ˆ˜๋ผ๊ณ  ๋ถ€๋ฅธ๋‹ค.

์ฃผ์–ด์ง„ ์ •์ˆ˜๊ฐ€ ์นด๋งˆ์ดํด ์ˆ˜์ธ์ง€ ํ…Œ์ŠคํŠธํ•˜๊ธฐ ์œ„ํ•œ ํ”„๋กœ๊ทธ๋žจ์„ ๋งŒ๋“ค์–ด๋ผ.

Input

์ž…๋ ฅ์€ ์—ฌ๋Ÿฌ ์ค„๋กœ ๊ตฌ์„ฑ๋˜๋ฉฐ ๊ฐ ์ค„์—๋Š” ์ž‘์€ ์–‘์˜ ์ •์ˆ˜ n(2

Output

์ž…๋ ฅ๋œ ๊ฐ ์ˆ˜์— ๋Œ€ํ•ด ์•„๋ž˜์— ์žˆ๋Š” ์ถœ๋ ฅ ์˜ˆ์— ๋‚˜์™€์žˆ๋Š” ์‹์œผ๋กœ ๊ทธ ์ˆ˜๊ฐ€ ์นด๋งˆ์ดํด ์ˆ˜์ธ์ง€ ์•„๋‹Œ์ง€๋ฅผ ํŒ๋‹จํ•œ ๊ฒฐ๊ณผ๋ฅผ ์ถœ๋ ฅํ•˜๋ผ.

Sample Input 

~cpp 
1729
17
561
1109
431
0

Sample Output 

~cpp 
The number 1729 is a Carmichael number.
17 is normal.
The number 561 is a Carmichael number.
1109 is normal.
431 is normal.

ํ’€์ด

์ž‘์„ฑ์ž ์‚ฌ์šฉ์–ธ์–ด ๊ฐœ๋ฐœ์‹œ๊ฐ„ ์ฝ”๋“œ
๋ฌธ๋ณด์ฐฝ C++ 3h 30m CarmichaelNumbers/๋ฌธ๋ณด์ฐฝ
์กฐํ˜„ํƒœ C . CarmichaelNumbers/์กฐํ˜„ํƒœ

์“ฐ๋ ˆ๋“œ

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:22:49
Processing time 0.0054 sec