TopCoder

餘切
$\Huge\text{freeh1}$

User's AC Ratio

92.3% (24/26)

Submission's AC Ratio

54.7% (41/75)

Tags

Description

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

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

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

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

Input Format

只有一行輸入。 輸入$n (1 \leq n \leq 1000)$、$m (1 \leq m \leq 1000)$、$k (0 \leq k \leq 1000)$,代表題目的$n,m,k$。

Output Format

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

Sample Input 1

2 5 2

Sample Output 1

1

Hints

練習一下遞迴吧! oaob

Problem Source

Subtasks

No. Testdata Range Score
1 0~3 100

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