[UVA] 11246 - K-Multiple Free set
|
|
K-Multiple Free Set |
|
|
Input: Standard Input Output: Standard Output |
|
|
A k-multiple free set is a set of integers where there is no pair of integers where one is equal to another integer multiplied by k. For example for k=2 {1,3,4} is a valid set. but not {2,4,5}. as 4 is double of 2.
You will be given n and k. you have to determine the largest k-multiple free subset of the integers from 1 to n.
Input
First line of the input contains T (1≤T≤1000) the number of test case. Then following lines contains T Test cases. Each case contains a line containing 2 integers n (1≤n≤1000000000) and k (2≤k≤100).
Output
For each test case output contains 1 integer the size of the largest k-multiple free subset of the integers from 1 to n.
Sample Input Output for Sample Input
|
3 10 2 100 2 1000 2
|
6 67 666
|
Problemsetter: Abdullah al Mahmud
Special Thanks: Shahriar Manzoor
在 1-n 的整數中，挑出最多個數的集合符合集合中兩兩不為另一個的 k 倍。
這題的思路很妙，假如現在給定 n = 10, k = 2,
{1,2,3,4,5,6,7,8,9,10} 考慮先將所有 2 個倍數去除
得到 {1,3,5,7,9} 這個集合內必然不會存在矛盾
那麼對於 {2,4,6,8,10} /k => {1,2,3,4,5}/k => {1,2}
再次從 {1,2} 挑出的答案*k*k 丟入原本的 => {1,3,4,5,7,9}
#include <stdio.h>
int f(int n, int k) {
if(n == 0) return 0;
if(n == 1) return 1;
return (n-(n/k)) + f(n/k/k, k);
}
int main() {
int testcase;
int n, k;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d %d", &n, &k);
printf("%d\n", f(n, k));
}
return 0;
}