把k的倍数的删去（k, 2k, 3k……），但是k^2不应该删去，因为k已经删去，所以不存在某个数乘上k之后为k^2
所以k^2可以留下，然后因为有k^2，所以k^3就是k^2的k倍，所以k^3要删去，但是k^4又要加回来，以此类推
ans = n - n / k + n / (k^2) - n / (k^3)……
见代码
#include<cstdio>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;int solve(int n, int k)
{int sign = 1, ans = 0;while(n){ans += sign * n;n /= k;sign *= -1;}return ans;
}int main()
{int n, k, T;scanf("%d", &T);while(T--){scanf("%d%d", &n, &k);printf("%d\n", solve(n, k));}return 0;
}