题解：UVA11246 选整数 K-Multiple Free set

joker_opof_qaq · 2024-08-10 19:58:31 · 题解

一眼结论题，准备好推式子。

首先，我们一定可以选择 n-\frac{n}{k} 只要我们不选所有 k 的倍数，那么就必然不会有两个数存在倍数为 k。但这真的是最优的吗。

我们发现，这样子 k^2 倍的数自然也会被删除，然而 k 的倍数已经没了，所以必然可以选 k^2 的倍数，此时我们的式子就更新为了 n-\frac{n}{k}+\frac{n}{k^2}。但是此时就出现错误了，因为 k^3 是 k^2 的倍数，所以再把它们减去，依此类推。

最终式子就是这样的 n-\frac{n}{k}+\frac{n}{k^2}-\frac{n}{k^3}+\frac{n}{k^4}-\frac{n}{k^5} \ldots 。

AC CODE:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<iomanip>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<list>
#include<stack>
#include<cctype>
#include<cstdlib>
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-48;ch=getchar();}
    return x*f;
}
inline void write(int x) {
    if (x<0)x=-x,putchar('-');
    if (x>9)write(x/10);
    putchar(x%10+'0');
}
int main(){
    int t=read();
    while(t--){
        int n=read(),k=read(),sum=0,cnt=1;
        int b=k;
        while(n){
            sum+=cnt*n;
            n=n/k;
            cnt=-cnt;
        }
        cout<<sum<<'\n';
    }
    return 0;
}

证明应该是最详细的吧。