首页 > 代码库 > hdoj 1097 A hard puzzle （找规律）

hdoj 1097 A hard puzzle （找规律）

2024-07-17 13:32:17   224人阅读

                              A hard puzzle

                           T   ime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
                                                 Total Submission(s): 29231    Accepted Submission(s): 10494


Problem Description
lcy gives a hard puzzle to feng5166,lwg,JGShining and Ignatius: gave a and b,how to know the a^b.everybody objects to this BT problem,so lcy makes the problem easier than begin.
this puzzle describes that: gave a and b,how to know the a^b‘s the last digit number.But everybody is too lazy to slove this problem,so they remit to you who is wise.
 

Input
There are mutiple test cases. Each test cases consists of two numbers a and b(0<a,b<=2^30)
 

Output
For each test case, you should output the a^b‘s last digit number.
 

Sample Input
7 668 800
 

Sample Output
96
 

AC  CODE:

#include<stdio.h>int main(){	int a,b;	while(~scanf("%d%d",&a,&b))	{		int i,temp,m,ans;		a%=10;		ans=a;		for(i=1;i<b;i++)		{			ans*=a;			ans%=10;			if(ans==a)			{				//printf("%d#",i);				temp=i;				m=(b-1)%temp;				for(i=0;i<m;i++)				{					ans*=a;					ans%=10;				}				break;			}		}		printf("%d\n",ans);	}	return 0;}


更简洁代码：

#include<stdio.h>main(){    int a,b,c;    while(~scanf("%d%d",&a,&b))    {        b%=4;a%=10;c=a;        if(b==0)        b=4;        while(--b)        c=c*a%10;        printf("%d\n",c);    }}


        两代码原理都一样，就是循环每次相乘得到结果的个位只与上次相乘的两个数的个位有关，而个位只有0~9这十个数，只需循环过程中对上次相乘的两个数都取余相乘再取余就能得到正确结果。拿34 100这对数据举例，其实只需计算4的100次方就行，但4的100次方也还是太大，计算机没有整型类型装的下，所以，可以4*4=16，对16取余得6再去乘4，这样连续运算100就能得到结果。

        但提交后会发现出现TEL错误。原因在于0<b<=2^30,若b=2^30，必然花大量的时间重复循环，导致提交出现TEL。

       其实可以通过找规律发现0~9最多连乘4次就会回到自身数值，例如，2连乘4个2为2*2*2*2*2=32，32对2取余得2，又回到数值2本身。所以，很多的循环是不必要重复的，只需b对4取余，再进行循环就能得到结果。这是第二个程序的中心思想。


联系
我们