3146.txt

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

Source

Problem Id:3146  User Id:fzk 
Memory:24K  Time:0MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>
#include <math.h>

int clac( int s, int p, int n ) {
	if( s < p )	return 0;
	return (s-n%s-1)*(n/s) + clac( s/p, p, n%s )*((n+s-1)/s);
}

int main( ) {
	int n, p, s, k=0, t;
	while( scanf( "%d%d", &p, &n ) == 2 && n ) {
		s = 1;
		while( s <= n/p )
			s *= p;
		t = clac( s, p, n );
		printf( "Case %d: %04d\n", ++k, (n+1-t)%10000 );
	}
	return 0;
}