P1045 压位60pts TLE求助

WD2c0mP @ 2023-01-08 12:11:50

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll mson[3100010], l;
void mul(ll x) {
    for (int i = 1; i <= l; i ++) {
        mson[i] *= x;
    }
    for (int i = 1; i <= l; i ++) {
        if (mson[i] > 9) {
            mson[i + 1] += mson[i] / 10;
            mson[i] %= 10;
        }
    }
    if (mson[l + 1]){
        l ++;
        while (mson[l] >= 10){
            mson[l + 1] += mson[l] / 10;
            mson[l] %= 10;
            l ++;
        }
    }
}
int main() {
    int p;
    scanf("%d",&p);
    mson[1] = l = 1;
    for (int i = 1; i <= p / 40; i ++) {
        mul(1099511627776);
    }
    p %= 40;
    for (int i = 1;i <= p;i ++){
        mul(2);
    }
    printf("%lld\n",l);
    for (int i = 1; i <= 500; i ++) {
        if (i != 500) printf("%lld",mson[500 - i + 1]);
        else printf("%lld",mson[500 - i + 1] - 1);
        if (i % 50 == 0 && i != 500) cout << endl;
    }

    return 0;
}

by acmwriter @ 2023-02-19 13:26:49

@OUOI 你压位肯定是压前500位，后面多出的不用管啊，相乘是从第一位开始乘的，只管前500位的变化就是了。

by acmwriter @ 2023-02-19 13:28:45

#include<bits/stdc++.h> 
using namespace std;
long long a[999999],n;
int main(){
    cin>>n;
    long long p=1,yw,j,b,c;
    a[1]=1;
    b=n/29;
    c=n%29+b;
    for(int i=1;i<=c;i++){
        yw=0;
        for(j=1;j<=p&&j<=500;j++){
            if(i<=b)a[j]=a[j]*536870912+yw;
            else a[j]=a[j]*2+yw;
            yw=a[j]/10;
            a[j]%=10;
        }
        while(yw>0){
            a[j]=yw%10;
            j++;
            yw/=10;
        }
        p=j-1;
    }
    for(int i=1;i<=p;i--){
        if(a[i]-1<0)a[i]=a[i]-1+10;
        else {
            a[i]-=1;
            break;
        }
    }
    cout<<(int)(n*log10(2))+1<<endl;
    for(int i=500;i>=1;i--){
        if(i>p)cout<<"0";
        else cout<<a[i];
        if((i-1)%50==0)cout<<endl;
    }
    return 0;
}

@OUOI 我这么压很轻松就过啦

by acmwriter @ 2023-02-19 13:37:38

@OUOI 数组从最高位开始存，也就是说数组的前500位就是所求值的后500位，只不过要用公式求它的最大位数。

by WD2c0mP @ 2023-02-19 13:43:46

e

by WD2c0mP @ 2023-02-19 13:44:05

都一个月了竟然还有人回

by _GW_ @ 2023-05-22 20:39:31

4个月了^v^

by WD2c0mP @ 2023-07-01 16:33:17

7个月了^v^