题目分析

给定贷款金额 ( P )、每月还款额 ( M )、还款期数 ( N )，要求计算该贷款的年利率（以百分比形式输出，保留一位小数）。
利率计算基于 现值公式，即所有未来还款的现值之和等于贷款金额 ( P )。

解题思路

核心公式

每月还款的现值之和应等于贷款金额： [ P = \sum_{i=1}^{N} \frac{M}{(1 + r)^i} ] 其中：

• ( r ) 是月利率，年利率为 ( 12r \times 100% )。
• 通过二分法求解 ( r )，使得现值之和逼近 ( P )。

关键步骤

1. 二分搜索：

   • 初始化搜索范围：( \text{low} = 0 )，( \text{high} = 1 )（即 0% 到 100% 年利率）。
   • 每次取中点 ( \text{mid} )，计算现值总和 ( \text{current} )。
   • 若 ( \text{current} > P )，说明利率偏低，调整 ( \text{low} = \text{mid} )；
   • 否则调整 ( \text{high} = \text{mid} )，直到区间足够小（精度 ( 10^{-8} )）。

2. 现值计算：

   • 对每个还款期数 ( i )，计算 ( \frac{M}{(1 + r)^i} ) 并累加。

3. 结果转换：

   • 将月利率 ( r ) 转换为年利率：( \text{rate} = 12r \times 100 )。

复杂度分析

• 时间复杂度：( O(N \log \frac{1}{\epsilon}) )，其中 ( \epsilon ) 是二分精度（( 10^{-8} )）。
• 空间复杂度：( O(1) )，仅需常数空间。

边界情况

1. 利率为 0：
   • 若 ( M \times N = P )，直接输出 0.0。
2. 高利率：
   • 当 ( M ) 远小于 ( P/N )，利率可能接近 100%。

解决代码

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;

double calculatePayment(double loan, double payment, int months, double rate) {
	double sum = 0.0;
	double temp = 1.0 + rate;
	double factor = 1.0;
	for (int i = 0; i < months; ++i) {
		factor /= temp;
		sum += payment * factor;
	}
	return sum;
}

double findRate(int P, int M, int N) {
	double low = 0.0;
	double high = 1.0;
	double mid = 0.0;
	double precision = 1e-8;
	
	while (high - low > precision) {
		mid = (low + high) / 2.0;
		double current = calculatePayment(P, M, N, mid);
		if (current > P) {
			low = mid;
		} else {
			high = mid;
		}
	}
	return mid * 100;
}

int main() {
	int P, M, N;
	cin >> P >> M >> N;
	double rate = findRate(P, M, N);
	cout << fixed << setprecision(1) << rate << endl;
	return 0;
}