第一题

设计一个函数，int getpoweredsum(int a,int b)，其中0<a<10 1<b<10000，功能是求出a^b的所有位的数字之和

c++

#include<stdio.h>
#include<string.h>
using namespace std;
const int N=1e4+10;
class Bignum
{
    public:
    short num[N];//num[0]存储个位
    int numcnt;//存储最高位所在的位置
    Bignum()
    {
        memset(num,0,sizeof num);
    }
    Bignum(int x)
    {
        memset(num,0,sizeof num);
        setNum(x);
    }
    void setNum(int x)
    {
        int tmpidx=0;
        while(x)
        {
            num[tmpidx++]=x%10;
            x/=10;
        }
        numcnt=tmpidx;
    }
    int getPoweredsum()
    {
        int ans=0;
        for(int i=0;i<numcnt;++i) ans+=num[i];
        return ans;
    }
    void printNum()
    {
        bool flag=0;
        for(int i=1e4+5;i>=0;--i)
        {
            if(flag||num[i]!=0)
            {
                printf("%d",num[i]);
                flag=1;
            }
        }
        printf("\n");
    }
    Bignum& operator =(const Bignum &W)
    {
        if(this==&W) return *this;
        memcpy(num,W.num,sizeof num);
        numcnt=W.numcnt;
        return *this;
    }
    Bignum operator *(const Bignum &W) const
    {
        Bignum ans;
        for(int i=0;i<numcnt;++i)
        {
            for(int j=0;j<W.numcnt;++j)
            {
                ans.num[i+j]+=num[i]*W.num[j];
                ans.num[i+j+1]+=ans.num[i+j]/10;
                ans.num[i+j]%=10;
            }
        }
        for(int i=1e4+5;i>=0;--i) if(ans.num[i]!=0) {ans.numcnt=i+1;break;}
        return ans;
    }
};
Bignum quickpower(int n,int x)//求n的x次方
{   
    Bignum tmp(n),ans(1);
    while(x)
    {
        if(x&1) ans=ans*tmp;
        tmp=tmp*tmp;
        x>>=1;
    }
    return ans;
}   
int getAns(int n,int x)
{
    Bignum t=quickpower(n,x);
    return t.getPoweredsum();
}
int main()
{
    Bignum t;
    int a,b;
    scanf("%d%d",&a,&b);
    printf("%d\n",getAns(a,b));
    return 0;
}

def cntsum(a, b):
    result=a**b
    digit_sum=sum(int(digit) for digit in str(result))
    return digit_sum
a = int(input("a"))
b = int(input("b"))
print(cntsum(a, b))

第二题

定义扩展某数列如下：

F(0)=0,F(1)=1 (n<2)

F(n)=47F(n-1)+99F(n-2) (n>1)

设计一个函数，该函数的功能是求出F(n)%c的值，其中n<2^62，c是小雨500的素数

c++

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 1e4 + 10;
class Bignum
{
public:
    short num[N]; // num[0] 存储个位
    int numcnt;

    Bignum()
    {
        memset(num, 0, sizeof num);
        numcnt = 1;
    }

    Bignum(int x)
    {
        memset(num, 0, sizeof num);
        setNum(x);
    }

    void setNum(int x)
    {
        numcnt = 0;
        while (x)
        {
            num[numcnt++] = x % 10;
            x /= 10;
        }
        if (numcnt == 0)
            numcnt = 1;
    }

    void printNum()
    {
        bool flag = 0;
        for (int i = numcnt - 1; i >= 0; --i  )
        {
            printf("%d", num[i]);
        }
        printf(" ");
    }

    Bignum operator*(const Bignum &W) const
    {
        Bignum ans;
        ans.numcnt = numcnt + W.numcnt; // 预估最大位数
        for (int i = 0; i < numcnt; ++i)
        {
            for (int j = 0; j < W.numcnt; ++j)
            {
                ans.num[i + j] += num[i] * W.num[j];
                ans.num[i + j + 1] += ans.num[i + j] / 10; // 进位
                ans.num[i + j] %= 10;
            }
        }
        // 计算最终有效位数
        while (ans.numcnt > 1 && ans.num[ans.numcnt - 1] == 0)
            ans.numcnt--; // 移除高位无效 0
        return ans;
    }

    Bignum operator+(const Bignum &W) const
    {
        Bignum ans;
        ans.numcnt = max(numcnt, W.numcnt);
        for (int i = 0; i < ans.numcnt; ++i)
        {
            ans.num[i] += num[i] + W.num[i];
            ans.num[i + 1] += ans.num[i] / 10; // 进位
            ans.num[i] %= 10;
        }
        if (ans.num[ans.numcnt])
            ans.numcnt++; // 处理最后的进位
        return ans;
    }

    Bignum operator%(int m) const
    {
        int remainder = 0;
        for (int i = numcnt - 1; i >= 0; --i) // 从最高位开始模拟除法
        {
            remainder = (remainder * 10 + num[i]) % m;
        }
        return Bignum(remainder);
    }
};

int toInt(Bignum x)
{
    int ans = 0;
    for (int i = min(10, x.numcnt) - 1; i >= 0; --i) // 修正：避免越界
    {
        ans = ans * 10 + x.num[i];
    }
    return ans;
}

int findCycleLength(int x)
{
    Bignum t1(1), t2(0);
    const Bignum tmp1(47), tmp2(99);

    int seen[600]; // 修正：只需要存储 0~10
    memset(seen, -1, sizeof seen);

    for (int i = 1; i <= 99; ++i)
    {
        Bignum t = tmp1 * t1 + tmp2 * t2;
        t2 = t1;
        t1 = t;
        int modVal = toInt(t % x);

        if (seen[modVal] != -1)
        {
            return i - seen[modVal]; // 计算循环节长度
        }
        seen[modVal] = i;
    }

    return -1; // 理论上不会发生
}

int main()
{
    long long n,time=0;
    scanf("%lld",&n);
    int cycleLength = findCycleLength(n);
    Bignum t1(1),t2(0);
    Bignum t3;
    const Bignum tmp1(47),tmp2(99);
    for(int i=2;i<=99;++i)
    {
        ++time;
        if(time==cycleLength) break;
        if(i%10==0) printf("\n");
        Bignum t;
        t = tmp1 * t1 + tmp2 * t2;
        t2=t1;
        t1=t;
        t3=t%n;
    }
    t3.printNum();
    return 0;
}