1150.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include "stdio.h"

int main( ) {
	int n, m, five, two, three, seven, nine, ans, a, b;
	while( scanf( "%d%d", &n, &m ) == 2 ) {
		m = n - m;
		
		five = two = three = seven = nine = 0;

		for( a=n; a; a/=2 )
			two += a/2;
		for( a=m; a; a/=2 )
			two -= a/2;

		for( a=n; a; a/=5 )
			five += a/5;
		for( b=m; b; b/=5 )
			five -= b/5;

		for( a=1; a<=n; a*=2 ) {
			for( b=a; b<=n; b*=5 ) {
				three += (n/b+7)/10;
				seven += (n/b+3)/10;
				nine += (n/b+1)/10;
			}
		}

		for( a=1; a<=m; a*=2 ) {
			for( b=a; b<=m; b*=5 ) {
				three -= (m/b+7)/10;
				seven -= (m/b+3)/10;
				nine -= (m/b+1)/10;
			}
		}

		ans = 1;

		if( five > two ) ans = 5;
		else if( two > five ) {
			two = ( two - five - 1 ) % 4 + 1;
			while( two-- )ans *= 2;
		}

		three = ( three - 1 ) % 4 + 1;
		while( three-- ) ans *= 3;
		seven = ( seven - 1 ) % 4 + 1;
		while( seven-- ) ans *= 7;
		nine = ( nine - 1 ) % 2 + 1;
		while( nine-- ) ans *= 9;

		printf( "%d\n", ans%10 );
	}
	return 0;
}