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