pku2773.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 53 行

#include <stdio.h>
int M, K;

int solve(int m, int k)
{
	int v, i, p[10], pid, x, j, ans;
	v = m;
	k--;
	for (i = 2, pid = 0; i <= m; i++)
	{
		if (m % i == 0)
		{
			p[pid++] = i;
			do
			{
				m /= i;
			}
			while (m % i == 0);
			v = v / i * (i - 1);
		}
	}
	if (m != 1)
	{
		v = m - 1;
	}
	for (i = 1, j = 0; j <= k % v; i++)
	{
		for (x = 0; x < pid; x++)
		{
			if (i % p[x] == 0)
			{
				break;
			}
		}
		if (x == pid)
		{
			j++;
			ans = i;
		}
	}
	return k / v * M + ans;
}

int main()
{
	while (scanf("%d %d", &M, &K) != -1)
	{
		printf("%d\n", solve(M, K));
	}
	return 0;
}