2773.txt

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

Problem Id:2773  User Id:fzk 
Memory:4160K  Time:125MS
Language:G++  Result:Accepted

Source 

#include "stdio.h"
#include "memory.h"

int s[1000010];
bool sign[1000010];
int gcd( int a, int b ) {
	int c;
	while( b ) {
		c = b;
		b = a%b;
		a = c;
	}
	return a;
}


int main( ) {
	int m, k, i, j, l;
	__int64 h;
	while( scanf( "%d %d", &m, &k ) == 2 ) {
		if( m == 1 ) {
			printf( "%d\n", k );
			continue;
		}
		memset( sign, 0, sizeof(bool)*m );
		s[0] = 1;
		for( i=2, j=1; i<m; i++ ) 
		if( !sign[i] ) {
			if( m % i == 0 ) {
				for( l=i; l<m; l+=i )
					sign[l] = true;
			}
			else
				s[j++] = i;
		}

		h = m;
		k--;
		printf( "%I64d\n",  h*(k/j) + s[k%j] );
	}

	return 0;
}