求助快速幂不知哪里错？？

zhutongxuan @ 2024-01-22 18:29:09

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

int p,base[1000],ans[2000],count;

void gjc(int a[],int b[],int c[]){
    int a1[1000],a2[1000];
    for(int i = 1;i <= 500;i++){
        a1[i] = a[i];
        a2[i] = b[i];
    }
    for(int i = 1;i <= 2000;i++){
        c[i] = 0;
    }
    for(int i = 1;i <= 500;i++){
        for(int j = 1;j <= 500;j++){
            c[i + j - 1] += a1[i] * a2[i];
            c[i + j] += c[i + j - 1] / 10;
            c[i + j - 1] %= 10;
        }
    }
}

int main(){
    cin>>p;
    double h = log10(2);
    cout<<(int)(h * p + 1)<<endl;
    ans[1] = 1;
    base[1] = 2;
    while(p != 0){
        if(p & 1 != 0){
            gjc(ans,base,ans);
        }
        gjc(base,base,base);
        p >>= 1;
    }
    ans[1]--;
    for(int i = 500;i >= 1;i--){
        cout<<ans[i];
        count++;
        if(count == 50){
            cout<<endl;
            count = 0;
        }
    }
    return 0;
}

by ikun_god @ 2024-01-27 12:32:59

鄙人表示看不懂马蜂

by jirunqi @ 2024-02-10 14:43:25

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ui = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;
const int mod = 1e9;
vector<int> a, b;
int p;

int quick_mul(int a, int b);
vector<int> mul(const vector<int> &a, const vector<int> &b);//高精度乘法
vector<int> quick_mul(const vector<int> &a, int b);//高精度快速幂
vector<int> sub(const vector<int> &a, const vector<int> &b);//高精度减法
int main(){
    a.push_back(1);
    b.push_back(2);
    cin >> p;
    a = quick_mul(b, p);
    a = sub(a, vector<int>(1, 1));

    int len = p*log10(2) + 1;
    cout << len << endl;
    while(a.size() < 500) a.push_back(0);
    int ct = 1;
    for (int i=499; i>=0; i--,ct++){
        cout << a[i];
        if(ct%50==0) cout << endl;
    }

    return 0;
}
vector<int> mul(const vector<int> &a, const vector<int> &b){
    int lna = a.size(), lnb = b.size();
    if(lna > 500) lna = 500;
    if(lnb > 500) lnb = 500;
    int len = lna + lnb;
    vector<int> c(lna+lnb);
    for (int i=0; i<lna; i++)
        for (int j=0; j<lnb; j++)
            c[i+j] += a[i]*b[j];
    //
    for (int i=0; i<len; i++){
        if(c[i] >= 10){
            if(i == len-1) c.push_back(0);
            c[i+1] += c[i]/10;
            c[i] %= 10;
        }
    }
    while(c.size()>1 && c.back()==0) c.pop_back();
    return c;
}
int quick_mul(int a, int b){//快速幂
    int ans = 1;
    int base = a;
    while(b){
        if(b&1) ans *= base;
        base *= base;
        b = b>>1;
    }
    return ans;
}
vector<int> quick_mul(const vector<int> &a, int b){//高精度快速幂
    vector<int> ans, base;
    ans.push_back(1);
    base = a;
    while(b){
        if(b&1) ans = mul(ans, base);
        base = mul(base, base);
        b = b >> 1;
    }
    return ans;
}
vector<int> sub(const vector<int> &a, const vector<int> &b){//高精度减法
    vector<int> c = a;
    for (int i=0; i<a.size() && i<b.size(); i++){
        c[i] = c[i] - b[i];
    }
    for (int i=0; i<c.size(); i++)
        if(c[i] < 0) c[i+1]--, c[i] += 10;

    return c;
}

by jirunqi @ 2024-02-10 14:48:11

如果暴力计算快速幂只能得到60分，最后输出只需要输出后面500位，所以计算乘法的时候，最多只需要计算500位\ 计算2^p-1\ 最后结果是输出10进制数，位数为len\ 那么2^p-1 = 10^{len}\ 位数的话，可以利用对数来求

by zhutongxuan @ 2024-03-02 22:19:17

@jirunqi 非常感谢！！