代码AC但耗时1.26ms,别人都是300ms,请问为什么那么慢

P1591 阶乘数码

holy @ 2022-12-26 10:06:28

#include<iostream>
#include<stdio.h>//scanf()
#include<cstring>//memset(数组名, 0, sizeof(数组名))
using namespace std;

int m[10000];

int main()
{
    int i, j, t;
    cin>>t;//将输入t组数据
    int c = 0;//保留进位
    int sum = 0;//中间值, c, sum在for内初始化会累加
    for(int k = 0; k < t; ++k)//这里不要声明i, 会被下面的i干扰
    {
        memset(m,0,sizeof(m));//对数组m初始化,防止连续输入后累加
        int n, a;
        scanf("%d %d", &n, &a);//n表示n的阶乘
        m[0] = 1;
//↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓核心代码↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
        for(i = 2; i <= n; ++i)
            for(j = 0; j < 10000; ++j)
            {
                sum = c + m[j] * i;
                m[j] = sum % 10;//保留个位数
                c = sum / 10;//保留进位
            }
//↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑核心代码↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑
        long long num = 0;//a出现的次数
        for(i = 10000; i >=0; --i)
            if(m[i] != 0)//数据开始出现
            {
                for(j = i; j >= 0; --j)
                    if(m[j] == a)
                        num++;
                break;//从a最后一个数输出到a[0]
            }
        cout<<num<<endl;
    }

    return 0;
}

by holy @ 2022-12-26 10:06:58

求助求助求助!!!


by Jerrlee✅ @ 2022-12-26 10:08:02

1.26ms /xia


by ppip @ 2022-12-26 10:09:05

1.26ms


by 035966_L3 @ 2022-12-26 10:11:08

@holy 乘法算到 3000 位即可,然后就快多了……


by Jerrlee✅ @ 2022-12-26 10:12:42

@holy O2+register=568ms


by Jerrlee✅ @ 2022-12-26 10:24:28

@holy 循环位数减一减就小于 200ms 了


by holy @ 2022-12-26 10:59:09

@Jerrlee✅ O2+register什么意思


by holy @ 2022-12-26 10:59:26

@wosizmcy 感谢?‍!


by holy @ 2022-12-26 10:59:46

@Jerrlee✅ 收到了解!


by Jerrlee✅ @ 2022-12-26 11:00:10

@holy 就是开 O2 优化,同时把循环里的 int 改为 register(也是一种优化)。


| 下一页