数列类型的题目，代码有了，但提交到系统时出现Time Limit Exceed，该怎么办？

编译与运行时无错误，提交到系统时出现 Time Limit Exceed。

题目描述

数列生成规则如下：

第一项的值为a,第二项的值为b, (0 ≤ a,b ≤ 9)
前两项之积，如果为一位数，则为本项的值；如果为两位数，则十位为本项，个位为后一项。

比如a=2,b=3,那么数列为2,3,6,1,8,8,...。请写一个程序，输出数列的第n个元素的值。

输入

第一行是一个整数n，表示样例的个数。每个样例的第一行是三个整数a,b,Q(1 ≤ Q ≤ 1,000),其中Q表示查询的次数。以后的Q行，每行一个整数y

,(1 ≤ n ≤ 1,000,000,000)。

输出

每个样例的每个查询输出一行，即对应元素的值。

样例输入

样例输出

#include<stdio.h>
int  main()
{
  int i,j;
  int k,l,m;
  int a,b,q;
  int n,y[1000];//n样例数。
  scanf("%d",&n);
  for ( i=0;i<n;i++ )
      { 
	    scanf("%d %d %d",&a,&b,&q);
        for ( j=0;j<q;j++ ) 
		   {
			scanf("%d",&y[j]);
		}
        j=2,l=0;
        if( y[l]==1 ) { printf("%d\n",a); l++; }
        if( y[l]==2 ) { printf("%d\n",b); l++; }
        while ( l<q )
           {
		       k=a*b;
                if ( k>=10 )
                { 
                        a=m=k/10; 
						j++; 
						if ( j==y[l] ) 
						 { 
						  printf("%d\n",m); l++;
						 }
                        b=m=k%10;
                }
                else
				 { 
				  a=b; b=m=k;
				 }
                j++;
				if ( j==y[l] ) 
				 { 
				  printf("%d\n",m); l++; 
				 }
            }
      }
      return 0;
}

编译与运行时无错误，提交到系统时出现 Time Limit Exceed。不知道怎么改了。希望能够得到更好的算法，能优化也行。谢谢。

双for 原因导致超时。建议申请空间去存储状态。

以后的Q行，每行一个整数y ,(1 ≤ n ≤ 1,000,000,000)。

可以预见的。你每次输一个需要查询的数。你就必须重新算一次。实际只需要算一遍。然后去下标里找就可以了。

你这里，我每次要来查询，我都要算一遍。我把这些个数组的值，直接存到数组里。我直接拿下标去取不就好了吗

我第一次来查的时候，查下标39...数列0-39已经算过了。

我第二次查1000,又从0-1000算一遍。

我第三次查100000 又从0-100000算一遍。

你发现问题没有。。

那是不是我存一个数组阿，第一次算到39.然后第二次要算1000的时候,我直接从39开始取就好了呀。

第三次，如果我要查999的数据，我直接从数组里拿。O(1)的速度。

您好，我是有问必答小助手，您的问题已经有小伙伴解答了，您看下是否解决，可以追评进行沟通哦~

如果有您比较满意的答案 / 帮您提供解决思路的答案，可以点击【采纳】按钮，给回答的小伙伴一些鼓励哦～～

ps:问答VIP仅需29元，即可享受5次/月有问必答服务，了解详情>>>https://vip.csdn.net/askvip?utm_source=1146287632