题解->

---

秦九韶be like:

秦九韶（1208—1268），字道古，祖籍鲁郡（今河南范县），出生于普州（今四川安岳），是南宋杰出的数学家，与李冶、杨辉、朱世杰并称宋元数学四大家，其著作与算法代表了当时世界数学的顶尖水平。

生平经历

• 家世与早年：

出身官宦世家，父亲秦季槱为进士，曾任工部郎中、秘书少监。秦九韶幼年随父在临安，得以向太史局官员学习天文历法，又师从隐者钻研数学，博学星象、音律、营造等多门学问。
仕途辗转：1231 年考中进士，历任县尉、通判、州守等职，辗转湖北、安徽、浙江等地为官；1261 年被贬至梅州，1268 年于任所逝世。
著作成书：1244—1247 年为母守孝期间，在湖州完成数学名著 《数书九章》，全书共 18 卷，列 81 题，涵盖天文、水利、赋役、军旅等诸多实际应用场景。
核心数学成就

• 大衍求一术（中国剩余定理）：

系统解决一次同余方程组的完整算法，这一成果比西方欧拉、高斯的同类研究早了 500 多年，至今仍是数论与密码学的基础工具之一。

• 正负开方术（秦九韶算法）：

求解任意高次方程正根的通用数值方法，采用迭代逼近与误差控制，等价于西方的霍纳法，但早了近 600 年。

• 三斜求积术：

给出已知三角形三边长度求面积的公式，与古希腊海伦公式等价，却为独立推导，体现了中国古代几何的实用智慧。

• 历史评价与影响：

秦九韶将数学紧密结合社会生产与政务实践，强调数学的 “经世务，类万物” 之用。《数书九章》长期被埋没，清代乾嘉学派重新发掘研究后，其价值才被广泛认可；近现代更被国际数学界推崇，成为连接古代东方算法与现代数值计算的重要桥梁。

秦九韶三大算法

1. 大衍求一术（中国剩余定理）

问题

$$\begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots \\ x \equiv a_n \pmod{m_n} \end{cases}$$

核心公式

$$M = \prod_{i=1}^n m_i$$

$$M_i = \frac{M}{m_i}$$

$$k_i M_i \equiv 1 \pmod{m_i}$$

$$x \equiv \sum_{i=1}^n a_i k_i M_i \pmod{M}$$

2. 正负开方术（秦九韶算法）

原始多项式

$$f(x) = a_n x^n + a_{n-1} x^{n-1} + \dots + a_1 x + a_0$$

嵌套形式

$$f(x) = (\dots((a_n x + a_{n-1})x + a_{n-2})x + \dots)x + a_1)x + a_0$$

递推公式

$$\begin{cases} v_0 = a_n \\ v_k = v_{k-1} \cdot x + a_{n-k} \quad (k=1,2,\dots,n) \\ f(x) = v_n \end{cases}$$

3. 三斜求积术

秦九韶公式

$$S = \frac{1}{2} \sqrt{a^2 b^2 - \left( \frac{a^2 + b^2 - c^2}{2} \right)^2}$$

海伦公式（等价）

$$p = \frac{a + b + c}{2}$$

$$S = \sqrt{p(p - a)(p - b)(p - c)}$$

---

进制转换的核心过程拆解（基于秦九韶算法）

先明确核心概念:

秦九韶算法的本质：把 $d₀×Kⁿ + d₁×Kⁿ⁻¹ + ... + dₙ×K⁰$ 转化为 $((...((d₀×K) + d₁)×K) + d₂)×K + ...) + dₙ$，逐位累积计算，避免直接算高次幂（如 16^8），既高效又减少溢出风险。

字符→数值映射：K 进制数的每一位（数字 / 字母）必须先转为十进制数值（如 'A'→10），才能参与计算

---

完整过程拆解（以 “16 进制数 1A” 为例）

输入：K=16，K 进制数 ="1A" → 目标：转十进制

• 步骤 1：初始化变量
  定义 long long ans= 0：存储最终的十进制结果，初始值为 0（累加的起点）
  遍历字符串 "1A" 的每一位字符：先处理 '1'，再处理 'A'
• 步骤 2：处理第一位字符 '1'
  判断 '1' 是数字字符，执行 '1' - '0' = 1，返回数值 1

执行秦九韶核心公式：

ans= ans * K + sum;
//sum是这一位数值;
//代入：ans = 0 * 16 + 1 = 1;

此时 ans= 1（完成第一位的计算）

• 步骤 3：处理第二位字符 'A'
  判断 'A' 是大写字母，执行 'A' - 'A' + 10 = 10，返回数值 10

再次执行核心公式：

ans= ans * K + sum;
// 代入值：ans = 1 * 16 + 10 = 26;

此时 ans= 26（完成所有位的计算）

• 步骤 4：输出结果
  最终返回 26，即 16 进制 1A 对应的十进制数

---

代码：

#include<iostream>
using namespace std;
int main(){
    int w;
    cin>>w;
    while(w--){
        int k;
        string m;
        cin>>n>>m;
        long long ans=0;
        for(int i=0;i<m.size();i++){
            int sum;
            if(m[i]>='0'&&m[i]<='9') sum=m[i]-'0';
            else sum=m[i]-'A'+10;
            ans=ans*k+sum;
        }
        cout<<ans<<endl;
    }
}