题解 - Wqh R13 - B

· · 题解

命题1 a_i=i^2。

证明 用数学归纳法。

当 i=1 时显然成立。

假设当 i=k 时命题成立，则当 i=k+1 时

4 \times k^2 \times a_{k+1}= (a_{k+1} + k^2-1)^2

即 4 \times k^2 \times a_{k+1}= a_{k+1}^2+k^4+1+2\times a_{k+1} \times k^2 - 2 \times a_{k+1}-2 \times k^2

即 a_{k+1}^2-2\times a_{k+1} \times (k^2+1)+k^4+1 -2 \times k^2=0

使用二次方程求根公式得

a_{k+1}=\displaystyle\frac{2 \times (k^2+1) \pm \sqrt{4 \times (k^2+1)^2-4 \times (k^2-1)^2}}{2} =k^2+1 \pm 2 \times k

因为 a_{k+1} >a_k=k^2，

所以 a_{k+1}=k^2+1-2 \times k=(k-1)^2 不成立，

只能 a_{k+1}=k^2+1+2 \times k=(k+1)^2。

即当 i=k+1 时命题也成立。

由数学归纳法可得命题正确。

由命题1，题意转化为计算 n^2 的值。

由于 n 的值有点大，使用高精度乘法通过此题。

10 分做法

#include<bits/stdc++.h>
#define int long long
// 不开 long long 也 10 分。
using namespace std;
signed main(){
    int n;
    cin>>n;
    cout<<n*n;
    return 0;
}

100 分做法

高精度。

#include<bits/stdc++.h>
using namespace std;
struct bint{
    int d,a[100010];
};
void input(bint& x){
    int t[100010],n=0;
    char c;
    while ((c=getchar())&&('0'<=c)&&(c<='9'))t[++n]=c-'0';
    for (int i=1;i<=n;i++){
        x.a[i]=t[n+1-i];
    }
    x.d=n;

}
void output(bint& x){
    for (int i=x.d;i>=1;i--){
        cout<<x.a[i];
    }
    cout<<endl;
}
bint mul(bint& x,bint& y){
    bint res;
    for (int i=1;i<=x.d;i++){
        for (int j=1;j<=y.d;j++){
            res.a[i+j-1]+=x.a[i]*y.a[j];
            while (res.a[i+j-1]>=10){
                res.a[i+j-1]-=10;
                res.a[i+j]++;

            }
        }
    }
    if ((x.d==1&&x.a[1]==0)||(y.d==1&&y.a[1]==0))res.d=1;
    else if (res.a[x.d+y.d]==0)res.d=x.d+y.d-1;
    else res.d=x.d+y.d;
    return res;
}
int main(){
    bint a,b,c;
    input(a);
    b=a;
    c=mul(a,b);
    output(c);
    return 0;
}