三而竭(数学函数求极限 蛮力)
题目名称：三而竭
时间限制：1000ms内存限制：256M
题目描述
一鼓作气再而衰三而竭。 小艺总是喜欢把任务分开做。 小艺接到一个任务，任务的总任务量是 n n n。 第一天小艺能完成 x x x 份任务。 第二天能完成 x k \frac{x}{k} kx … 第 t t t 天能完成 x k ( t − 1 ) \frac{x}{k^{(t-1)}} k(t−1)x。 小艺想知道自己第一天至少完成多少才能完成最后的任务。
输入描述：
第一行输入整数 n , k n,k n,k (1<=n<=1e9,2<=k<=10)
输出描述：
输出x的最小值。
示例
示例1
输入
59 9
输出
54
题解 or 思路：
每天完成的任务量是一个等比数列
设： 第一天完成的任务量为
x
x
x, 一共做任务的天数为
n
u
m
num
num
根据等比求和公式得：
x
∗
(
1
−
(
1
k
)
n
u
m
)
1
−
1
k
\frac{x * (1 - (\frac{1}{k})^{num})}{1 - \frac{1}{k}}
1−k1x∗(1−(k1)num)
当
n
u
m
num
num 取正无穷的时候可得：
x
1
−
1
k
\frac{x}{1 - \frac{1}{k}}
1−k1x
令：
x
1
−
1
k
\frac{x}{1 - \frac{1}{k}}
1−k1x
≥
\ge
≥ n
整理得：
x
≥
n
∗
(
1
−
1
k
)
x \ge n * (1 - \frac{1}{k})
x≥n∗(1−k1)
我们让
x
=
n
∗
(
1
−
1
k
)
x = n * (1 - \frac{1}{k})
x=n∗(1−k1) 向上取整
我们根据发现 最后我们算出的答案可能会偏小（这个也不难去理解）
但根据我们推的
x
x
x 已经可以确定出相对的值，接下来我们暴力去枚举
x
x
x, 找到第一个满足即为本题答案
AC 代码如下：
#include <stdio.h>
int solution(int n, int k){
int result;
// TODO: 请在此编写代码
result = ((long long)n * (k - 1) + k - 1) / k;
for (result; ; result++)
{
int sum = result, t = result;
while (t)
{
if (sum >= n)
return result;
sum += t / k, t /= k;
}
if (sum >= n)
return result;
}
}
int main() {
int n;
int k;
scanf("%d", &n);
scanf("%d", &k);
int result = solution(n, k);
printf("%d", result);
return 0;
}