杭电1061超时，求修改

显示全部楼层 · 2010-7-19 02:55:42

#include
using namespace std;
int main()
{
int n,i,s,u,loop,pri;
long long t;
cin>>n;
while(n--)
{
cin>>t;
if(t==1) cout<<1;
else if(t==2) cout<<4;
else if(t==3) cout<<7;
else
{
u=t%10;s=1;pri=0;loop=1;
for(i=0;i<t;i++)
{

s=s*u%10;

if(s==u && i)

{

loop=i;

pri=1;

}

if(pri) break;
}
if(loop==1)

cout<<u;
else
{

s=u;

for(i=0;i<(t-1)%loop;i++)

{

s=s*u%10;

}

cout<<s;
}
}
if(n) cout<<endl;
}
}
http://acm.hdu.edu.cn/showproblem.php?pid=1061
1楼仍然超时诶。。
2楼看不懂

千问 · 2010-7-19 02:55:42

超时？那就找规律吧。对0结尾的数无论自乘多少次还是0，以1结尾的数无论自乘多少次还是1，以2结尾的数自乘0次为2，自乘1次2*2为4，自乘2次2*2*2为8，自乘3次2*2*2*2=16为6，自乘4次2*2*2*2*2=32为2，自乘5次2*2...为4，看出来了吧，循环了，其序列为2，4，8，6。好，再看3的尾数，1次方为3，2次方为9，3次方为7，4次方为1，5次方为3，又循环了，其序列为3，9，7，1。之后4到9的尾数序列会构造了吧。定义数组a[10][10]，用a[0]存储数字i的序列数的个数（i=0，1，2...，8，9），其数组为：int a[10][10]=
{
{1,0},

千问 · 2010-7-19 02:55:42

你看N的范围 1<=N<=1,000,000,000 所以你这么做肯定是会TLE的。其实这题是有规律可循的，只要看N的个位数即可。而且最右边的数每四次一循环。比如3^1=3,3^2=9,3^3=27,3^4=81,3^5=243,3^6=729…… 个位数已经循环了。//我的代码供参考int main (){
int t,i

千问 · 2010-7-19 02:55:42

有不明白的地方可以到杭电forum查看他人的经验..也可以提交自己的心得http://acm.hdu.edu.cn/forum/^_^....里面有很多值得学习和探讨的东东哦!!!比如1061这题最短AC代码:main(N,a){for(;scanf("%d",&a)+1;N=0)N||puts(L"00001111624813976