自动搬运

查看原文

来自洛谷，原作者为

	NightTide 我回来了

搬运于2025-08-24 22:34:01，当前版本为作者最后更新于2022-08-23 22:34:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

PART 0：说些闲话

这是去年十月份打的比赛，应该算我打的第一场月赛吧，最近突然想起来就来看看，发现还可以交题解就写一篇。

我才不会说是来贺快读模板的呢

PART 1：题目大意

在 $[1,n]$ 中取若干个整数，使得 $k$ 和 $k \times p$ 不同时被选中，求最多能够选择多少个整数。

PART 2：解题思路

首先阐述一下我们的策略，从大往小去选，一旦这个数 $k$ 可以被选择，也就是说 $k\times p$ 没有被选择，我们就选取它，这样一定是最优的。这是本蒟蒻比赛时的猜测。

当时水平太弱，误打误撞写出了正解，现在来想想为什么这样是对的？

原因很简单。我们依照这种方式，可以把 $[1,n]$ 上的整数分为若干段：$(\dfrac{n}{p},n],(\dfrac{n}{p^2},\dfrac{n}{p}],(\dfrac{n}{p^3},\dfrac{n}{p^2}],(\dfrac{n}{p^4},\dfrac{n}{p^3}]\dots$。总共是 $\left\lceil\log_pn\right\rceil$ 段，其中，第 $i$ 段所含有的元素个数是 $\dfrac{n(p - 1)}{p^i}$ 个。这样分段有什么好处呢？我们很容易发现，同一段中的任意数都可以被同时选中，于是我们来考虑一段一段的选。显而易见，选取越靠前的段，最终得到的元素个数就越多，所以显然是尽可能地选取较大的数，也就是我们这里较靠前的段是最优的。同时我们发现，相邻的两段是不能够被同时选取的，也就是说，最终的策略是选取第 $1,3,5,7,\dots$ 段。

但是这样实现起来似乎很复杂，有没有什么简单的方式呢？

当然是有的，这里先放出代码来：

long long ans = 0;
for(long long i = 1; n > 0; i = -i, n /= p){
	ans += i * n;
}
printf("%lld\n",ans)

模拟一下即可理解：先加上 $n$，然后减去 $\dfrac{n}{q}$，再加上 $\dfrac{n}{q^2}$，……以此类推，这样的结果就和上面我们说的策略是一样的了。

PART 3：完整代码

#include<bits/stdc++.h>
#define MAXN 1000010
using namespace std;
long long t,n,p;
bool vis[MAXN];
inline long long read(){
   long long s = 0, w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9') { if(ch == '-') w = -1; ch = getchar(); }
   while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
   return s * w;
}
int main(){
	t = read();
	while(t--){
		n = read(); p = read();
		if(p == 1){
		    printf("0\n");
		    continue;
		}
		long long ans = 0;
		for(long long i = 1; n > 0; i = -i, n /= p){
			ans += i * n;
		}
		printf("%lld\n",ans);
	}
}