[UVa] 10212 - The Last Non-zero Digit

題目網址: http://goo.gl/0GluUR

題意:
(from luckycat)


解法: 因為UVA的時限到10秒...，所以可以用簡單一點的方法，會產生末位數的 0 ，必定是 2 跟 5 的因數相乘，所以就檢查 N 到 (N-M+1) 的 2、5 因數個數的差，同時將剩下來的數累乘 mod 10，最後補上 2 或 5 的剩餘次方數 mod 10 即是答案。但是UVA跑完測資要4秒...。
另一個較快的方法，詳細說明在此 http://blog.sina.com.cn/s/blog_64018c250100u59n.html。

TAG: Math

注意:

程式碼:

	/**
	* Tittle: 10212 - The Last Non-zero Digit.
	* Author: Cheng-Shih, Wong
	* Date: 2015/05/19
	*/
	// 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) )
	typedef long long ll;
	// declarations
	ll n, m;
	ll ans, k;
	// functions
	// main function
	int main( void )
	{
	ll u, v, tmp;
	// input
	while( scanf( "%lld%lld", &n, &m )==2 ) {
	// solve
	ans = 1LL;
	k = 0LL;
	for( u=n, v=(n-m+1); u>=v; --u ) {
	tmp = u;
	while( (tmp%2LL) == 0 ) {
	tmp /= 2LL;
	++k;
	}
	while( (tmp%5LL) == 0 ) {
	tmp /= 5LL;
	--k;
	}
	ans = (ans*tmp)%10LL;
	}
	if( k > 0 ) {
	for( u=1; u<=k; ++u )
	ans = (ans*2LL)%10LL;
	} else {
	for( u=1; u<=-k; ++u )
	ans = (ans*5LL)%10LL;
	}
	printf( "%lld\n", ans );
	}
	return 0;
	}

view raw 10212 - The Last Non-zero Digit.cpp hosted with ❤ by GitHub