#include <stdio.h>

int N, K;
int d[1000000], Cnt;

int gcd ( int a, int b ){
	int c;
	
	for (;;){
		if (a%b==0) return b;
		c=a, a=b, b=c%b;
	}
}

int main (){
	int i;
	
	while ( scanf ( "%d%d", &N, &K )!=EOF ){
		K--;
		for (i=1, Cnt=0; i<=N; i++) if (gcd(N,i)==1) d[Cnt++]=i;
		printf ( "%d\n", d[K%Cnt]+N*(K/Cnt) );
	}
	
	return 0;
}

• gcd is too slow (413) frkstyc 2006-03-28 02:57:47