uva 11246 - K-Multiple Free set(數論)

題目鏈接：uva 11246 - K-Multiple Free set

題目大意：給定n，k。求一個元素不大於n的子集，要求該子集的元素盡量多，並且不含兩個數滿足a?k=b.

解題思路：容斥原理，f(i)=(?1)inki,取f函數的和即可。

#include 
#include 
#include 

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;
}