求dalao指错,2个TLE

P1045 [NOIP2003 普及组] 麦森数

Michaelwrl @ 2017-08-21 18:17:45

贴代码(请大佬指点下)

、、、

#include <bits/stdc++.h>
using namespace std;
int f[505];
void mul(int a) {
    int i, j, k, tmp = 0;
    for(i = 0; i < 500; i++) {
        tmp = tmp + f[i] * a;
        f[i] = tmp % 10;
        tmp = tmp / 10;
    }
}
void sub(int x) {
    f[0] -= x;
    int k = 0;
    while(k < 500 && f[k] < 0) {
        f[k] = f[k] + 10;
        f[k + 1]--;
        k++;
    }
}
int main() {
    int n;
    while(scanf("%d", &n) != EOF) {
        int i, j, k;
        memset(f, 0, sizeof(f));
        f[0] = 1;
        for(i = 0; i < n / 10; i++)mul(1024);
        for(i = 0, k = 1; i < n % 10; i++)k = k * 2;
        mul(k);
        sub(1);
        printf("%d\n", int(n * log(2) / log(10) + 1));
        for(i = 0, k = 499; i < 10; i++) {
            for(j = 0; j < 50; j++) {
                printf("%d", f[k]);
                k--;
            }
            printf("\n");
        }
    }
    return 0;
}、、、

by Michaelwrl @ 2017-08-21 18:19:05

虽然是棕名,还是请大佬们花点时间看一下QAQ


by zhylj @ 2017-08-21 18:39:04

压位或者快速幂


by Michaelwrl @ 2017-08-22 17:08:02

@郑皓元 可以详细点么,完全不造啥意思


by wjy666 @ 2017-08-28 16:39:36

这没问题啊,跟我的基本一样


by totorato @ 2017-11-01 21:54:54

比如这样:for(int i=1;i<=n/25;i++)mul(a,33554432);

for(int i=1;i<=n%25;i++)mul(a,2);

其中mul函数是将高精度整数a乘上后面的int


by totorato @ 2017-11-01 21:55:32

@boshi 可以稍微快一点


|