[UVa] 10162 - Last Digit

題目網址: http://goo.gl/k0k4Ff

題意:
(from luckycat)


解法: 找規律，先求出 1 ~ 9 每個數字的次方循環，發現最大的循環不超過 4，因為 4 能夠整除100，就會發現 d^i = d^(i%100)，利用這樣的性質，就可以求出答案。

TAG: ad hoc

注意:

程式碼:

	/**
	* Tittle: 10162 - Last Digit
	* Author: Cheng-Shih, Wong
	* Date: 2015/04/15
	*/
	// include files
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	// declarations
	char buf[3000];
	int sl, ans;
	int cycle[10] = { 0, 1, 4, 4, 2, 1, 1, 4, 4, 2 };
	int val[10][10] = {
	{},
	{ 1 },
	{ 6, 2, 4, 8 },
	{ 1, 3, 9, 7 },
	{ 6, 4 },
	{ 5 },
	{ 6 },
	{ 1, 7, 9, 3 },
	{ 6, 8, 4, 2 },
	{ 1, 9 }
	};
	// functions
	// main function
	int main( void )
	{
	int t, v;
	int sum100;
	// init
	sum100 = 0;
	FOR( i, 1, 99 ) {
	t = i%10;
	if( t == 0 ) continue;
	sum100 = (sum100+val[t][i%cycle[t]])%10;
	}
	// input
	while( scanf( "%s", buf )==1 && strcmp(buf,"0") ) {
	// solve
	sl = strlen( buf );
	ans = 0;
	if( sl >= 3 ) {
	t = buf[sl-3]-'0';
	ans = (ans+t*sum100)%10;
	}
	t = 0;
	if( sl >= 2 ) t += 10*(buf[sl-2]-'0');
	t += buf[sl-1]-'0';
	FOR( i, 1, t ) {
	v = i%10;
	if( v == 0 ) continue;
	ans = (ans+val[v][i%cycle[v]])%10;
	}
	// output
	printf( "%d\n", ans );
	}
	return 0;
	}

view raw 10162 - Last Digit.cpp hosted with ❤ by GitHub