樂(lè)樂(lè)是一個(gè)聰明而又勤奮好學(xué)的孩子。他總喜歡探求事物的規(guī)律。一天,他突然對(duì)數(shù)的正整數(shù)次冪產(chǎn)生了興趣。
眾所周知,2的正整數(shù)次冪最后一位數(shù)總是不斷的在重復(fù)2,4,8,6,2,4,8,6……我們說(shuō)2的正整數(shù)次冪最后一位的循環(huán)長(zhǎng)度是4(實(shí)際上4的倍數(shù)都可以說(shuō)是循環(huán)長(zhǎng)度,但我們只考慮最小的循環(huán)長(zhǎng)度)。類似的,其余的數(shù)字的正整數(shù)次冪最后一位數(shù)也有類似的循環(huán)現(xiàn)象:
循環(huán)
循環(huán)長(zhǎng)度
2
2、4、8、6
4
3
3、9、7、1
4
4
4、6
2
5
5
1
6
6
1
7
7、9、3、1
4
8
8、4、2、6
4
9
9、1
2
這時(shí)樂(lè)樂(lè)的問(wèn)題就出來(lái)了:是不是只有最后一位才有這樣的循環(huán)呢?對(duì)于一個(gè)整數(shù)n的正整數(shù)次冪來(lái)說(shuō),它的后k位是否會(huì)發(fā)生循環(huán)?如果循環(huán)的話,循環(huán)長(zhǎng)度是多少呢?
注意:
1. 如果n的某個(gè)正整數(shù)次冪的位數(shù)不足k,那么不足的高位看做是0。
2. 如果循環(huán)長(zhǎng)度是L,那么說(shuō)明對(duì)于任意的正整數(shù)a,n的a次冪和a + L次冪的最后k位都相同。
輸入只有一行,包含兩個(gè)整數(shù)n(1 <= n < 10100)和k(1 <= k <= 100),n和k之間用一個(gè)空格隔開(kāi),表示要求n的正整數(shù)次冪的最后k位的循環(huán)長(zhǎng)度。
輸出一行,這一行只包含一個(gè)整數(shù),表示循環(huán)長(zhǎng)度。如果循環(huán)不存在,輸出-1。
32 2
4
比賽時(shí)間為四個(gè)小時(shí),題目難度不保證正序排列,請(qǐng)合理分配時(shí)間?。ㄒ蜒悠冢?/p>