Description

"考拉茲猜想(英語:Collatz conjecture),又稱為奇偶歸一猜想3n+1猜想冰雹猜想角谷猜想哈塞猜想烏拉姆猜想敘拉古猜想,是指對於每一個正整數,如果它是奇數,則對它乘3再加1,如果它是偶數,則對它除以2,如此循環,最終都能夠得到1。" - 維基百科

小龍讀到這個猜想的時候覺得很神奇,竟然會有這種事情! 於是他突發奇想,決定想要給你n,m,k,讓你輸出所有從1到n,考拉茲猜想進行的步驟中最大數字模(%)mk的數字總共有幾個,你覺得你有辦法做到嗎?

定義考拉茲猜想進行的步驟為一個數字做到1所需要的步驟數。

範例: num= 6: 6->3->10->5->16->8->4->2->1。 共8個步驟,16為過程中的最大值。

Input Format

只有一行輸入。 輸入n(1n1000)m(1m1000)k(0k1000),代表題目的n,m,k

Output Format

請輸出題目所要求的答案。

Sample Input 1

2 5 2

Sample Output 1

1

Hints

練習一下遞迴吧! oaob

Subtasks

No. Testdata Range Score
1 0~3 100

TopCoder

餘切
freeh1

User's AC Ratio

90.7% (39/43)

Tags

Problem Source

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Memory Limit (RSS, KiB) Output Limit (KiB) Subtasks
0 1000 250000 250000 65536 1
1 1000 250000 250000 65536 1
2 1000 250000 250000 65536 1
3 1000 250000 250000 65536 1