UVA 11246 K-Multiple Free Set：容斥原理求無 k 倍關係子集最大尺寸

問題描述

給定 n, k，從 {1..n} 中選最大子集，使不存在 a, b 滿足 a*k = b。輸出最大尺寸。

數學解法：容斥 / 遞推

考慮將數按 k 進制分層。等價於：

ans = Σ_{i≥0} (-1)^i * floor(n / k^i)

即交替加減 n, n/k, n/k^2, ... 直到為 0。這是容斥原理在「排除 k 倍關係」上的直接應用。

完整參考代碼

#include <cstdio>
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 = -sign;
    }
    return ans;
}
int main(){
    int T; scanf("%d",&T);
    while(T--){
        ll n,k; scanf("%lld%lld",&n,&k);
        printf("%lld\n", solve(n,k));
    }
    return 0;
}

總結

UVA 11246 通過觀察 k 進制層級關係，得出簡潔的交替求和公式，O(log_k n) 時間解決，是數論與容斥結合的優美例題。