Timus - 1110. Power 除尽问题

You are given the whole numbersN,MandY. Write a program that will find all whole numbersXin the interval [0,M− 1] such thatXNmodM=Y.

Input

The input contains a single line withN,MandY(0<N<999, 1<M<999, 0<Y<999) separated with one space.

Output

Output all numbersXseparated with space on one line. The numbers must be written in ascending order. If no such numbers exist then output −1.

Sample

input output

2 6 4	2 4

这个需要计算pow(x, n)，那么数值肯定很大，如果使用大数乘法来算这道题是可以的，但是我试过会超时，所以这里只能取巧了。

思路： 相乘之后取模和相乘之中任何时候取模的结果都是一样的，利用这个特性就可以做出这道题目来.

下面程序多次相乘之中取模，和最后乘完再取模的到的结果是一样的，所以本程序结果正确，速度也很快。

void Power1110_2()
{
	int n, m, y;
	cin>>n>>m>>y;
	bool has_num = false;
	for (int i = 0; i < m; i++)
	{
		int ans = i;
		for (int j = 1; j < n; j++)
		{
			ans *= i;
			ans %= m;
		}
		if (ans == y)
		{
			has_num = true;
			cout<<i<<' ';
		}
	}
	if (!has_num) cout<<-1;
}