题目链接：uva 11246 - K-Multiple Free set

题目大意：给定n，k。求一个元素不大于n的子集，要求该子集的元素尽量多，而且不含两个数满足a∗k=b.

解题思路：容斥原理。f(i)=(−1)inki,取f函数的和就可以。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

ll solve (ll n, ll k) {

    ll ans = 0, sign = 1;

    while (n) {

        ans += sign * n;

        n /= k;

        sign *= -1;

    }

    return ans;

}

int main () {

    int cas;

    scanf("%d", &cas);

    while (cas--) {

        ll n, k;

        scanf("%lld%lld", &n, &k);

        printf("%lld\n", solve(n, k));

    }

    return 0;

}