Problem 1277 --K-ary tree
1277: K-ary treeTime Limit: 1 Sec Memory Limit: 128 MB
Submit: 866 Solved: 224
Given a complete K-ary tree with N nodes, please find the number of leaf nodes of this tree.
a K-ary tree is a rooted tree where every internal node has at most K child nodes, a K-ary tree of height h is complete if
- Level 0,1,...,h-1 are all full
- At level h, the leaf nodes are as far left as possible.
The first line will be an integer \(T (1 \leq T \leq 1000)\), which is the number of test cases.
For each test data:
The first line contains two integer N \((2 \leq N \leq 10^8 )\) and K \((2 \leq K \leq 100 )\) — the number of nodes, and the number child nodes it has at most.
For each test cases, print one line with one integer, the number of leaf nodes of this tree