2 9 10超时 大佬求调

P1045 [NOIP2003 普及组] 麦森数

oulu @ 2024-11-15 11:12:28

#include <stdio.h>
#include <math.h>
int num[510];
void fac(int a[], int x)
{
    int jw = 0;
    for (int j = 0; j < 510; j++)
    {
        a[j] = a[j] * x+jw;
        jw = a[j] / 10;
        a[j] %= 10;
    }

}
void sub(int num[])
{
    for (int j = 0; j < 510; j++)
    {
        if (num[j] - 1 < 0)
        {
            num[j] = num[j] + 10 - 1;
            num[j + 1] -= 1;
        }
        else
        {
            num[j] -= 1;
            break;
        }
    }
}
int main() {
    int p;
    scanf("%d", &p);
    printf("%d\n", (int)floor(p * log10(2)) + 1);
    num[0] = 1;
    for (int i = 0; i < p; i++)
    {
        fac(num, 2);
    }
    sub(num);
    int cnt = 1;
    for (int j = 499; j >= 0; j--)
    {
        printf("%d", num[j]);
        if (cnt % 50 == 0) {
            printf("\n");
        }
        cnt++;
    }
    return 0;
}

by template_ @ 2024-12-31 13:22:42

首先不用打sub函数,因为2的正整数次幂最后一位都是2,4,8,6循环。直接减就好了

超时:建议学一下快速幂(求2的n次方等价于求2的n/2次方再平方,n是奇数再×2)


|