题目链接: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;
}
分享到:
相关推荐
算法-数论- 斐波那契数列(Fibonacci).rar
算法-数论- 概述.rar
算法-数论- 约数.rar
算法-数论- 逆元.rar
算法-数论- 欧拉函数.rar
算法-数论- 莫比乌斯反演.rar
算法-数论- 快速幂.rar
算法-数论- 素性测试.rar
算法-数论- 整式方程.rar
算法-数论- 整数分解.rar
算法-数论- 毕达哥拉斯三元组.rar
算法-数论- 线性同余方程.rar
算法-数论- 整除与同余.rar
算法-数论- 佩尔方程与连分数.rar
算法-数论- 逆元与同余式定理.rar
好的资源,学好数论。教材整理-新课标其它.zip,请好好好好好好好哦啊
算法-数论- 最大公约数与最小公倍数.rar
算法-数论- 高次同余方程与 BSGS 算法.rar
ACM---算法数论