C - Last Digit

Description

The function
f(n, k) is defined by f(n, k) = 1^k + 2^k + 3^k +...+
n^k. If you know the value of n and k, could you tell us the last digit of
f(n, k)?

For example, if n is 3 and k is 2, f(n,
k) = f(3, 2) = 1² + 2² + 3² = 14. So the last digit of
f(n, k) is 4.

Input

The first line has an integer
T (1 <= T <= 100), means there are T test cases.

For each test case, there is only one line with two integers n,
k (1 <= n, k <= 10⁹), which have the same meaning as above.

Output

For each test case, print the last digit of
f(n, k) in one line.

Sample Input

10

1 1

8 4

2 5

3 2

5 2

8 3

2 4

7 999999997

999999998 2

1000000000 1000000000

Sample Output

打表发现n的循环周期可以是100，所以直接n%100,发现m的循环周期可以是4，所以只要在a[100]储存4个数

#include<stdio.h>

#include<string.h>

int a[100];

int quick(int a,int b)

{

	int ans=1;

	a=a%10;

    while(b>0)

    {

    	if(b%2==1)

    	ans=ans*a%10;

    	b=b/2;

    	a=(a*a)%10;

    }

    return ans;

}

int main()

{

	int i,n,k,t,j,T;

	scanf("%d",&T);

	while(T--)

	{

	 scanf("%d%d",&n,&k);

	 n=n%100;

	 for(i=1;i<=4;i++)

	 {

	   t=0;

	   for(j=1;j<=n;j++)

	   {

		t=(t+quick(j,k))%10;

	   }

	   a[i]=t;

	 }

	 a[0]=a[4];

	 k=k%4;

     printf("%d\n",a[k]);

	}

	return 0;

}

另一种是先找循环节，再算

#include<stdio.h>

#include<string.h>

int powermod(int n,int k){

	int ans=1;

	n=n%10;

	while(k){

		if(k%2) ans=(ans*n)%10;

		k=k/2;

		n=(n*n)%10;

	}

	return ans;

}

int main(){

	int T,i,j,n,k;

	scanf("%d",&T);

	while(T--){

		int f[1111]={0};

		int ans=0,t=0;

		scanf("%d%d",&n,&k);

		for(i=1;i<=1000;i++){

			t=powermod(i,k);

			f[i]=(t+f[i-1])%10;

		}

		int temp,flag;

		for(i=1;i<=1000;i++){

			flag=1;

			for(j=i+1;j<=1000;j++){

				if(f[j]!=f[j%i]) {flag=0; break;}

			}

			if(flag) {temp=i; break;}

		}

		ans=n%temp;

		printf("%d\n",f[ans]);

	}

}

巴特西

C - Last Digit

最新文章

热门文章