Description

现有一公式：a^b mod c = X.给出a,b,c，求X。


注：c总是素数

Input

Output

Sample Input


3 8 13
2 3 11

Sample Output

3
8

Description

现有一公式：X^a mod b = c.给出a,b,c，求出所有满足条件的X。
输入包括多组数据，每组数据三个正整数1<=a,b,c<=10^7。
每组数据输出若干行，每一行代表了满足方程的一个X的解，解的顺序按照从小到大输出,最后输出一个空行。
没有解输出“No Solution!”

注：b总是素数

Input

Output

Sample Input


3 13 8
2 3 2

Sample Output


2
5
8

        static void Main(string[] args)
        {
            int r = 0;
            r = Fx(3, 8, 13);
            Console.Write(r);
            r = Fx(2, 3, 11);
            Console.Write(r);
            Console.Read();
        }

        static int Fx(int a, int b, int c)
        {
            int t = b >> 1;
            return (t>0?Fx((a*a)%c,t,c):1)*((b & 1)==0?1:a % c) % c;
        }

------解决方案--------------------
探讨

引用:

问题1
C# code
static void Main(string[] args)
{
int r = 0;
r = Fx(3, 8, 13);
Console.Write(r);
r = Fx(2, 3, 11);
Console.Wr……

大牛出现了！
求数学思想，求解释！
求第二题，求帮助！


------解决方案--------------------
C# code

// Right-to-left binary method
int Modular(int theBase, int exponent, int modulus)
{
    int result = 1;
    while( exponent > 0 )
    {
        if( (exponent & 1) == 1 )
        {
            result = (result * theBase) % modulus;
        }
        exponent /= 2;
        theBase = (theBase * theBase) % modulus;
    }
    return result;
}

------解决方案--------------------
第二题只想到这么一个算法
C# code
        static void FX2(int a, int b, int c)
        {
            while (c < 10000000)
            {
                double x = Math.Pow( Math.E ,Math.Log(c)/a);
                if (Math.Round( x,8) == Math.Round(x))
                {
                    Console.WriteLine(Math.Round(x));
                }
                c += b;
            }            
        }

------解决方案--------------------
a^b mod c = X
首先计算a^1 mod c = ? a^2 mod c = ? ,直到a^n mod c =1,然后n为循环，计算b mod n，最后求出余数。
3^8 mod 13 = 9 ,不是3

------解决方案--------------------
第二题真没看懂,假定a=3 b=13 c=8

由 X^3 mod 13 = 8 可以推导得出 X^3=13*k +8(k为自然数)
由于k有无数个，可以推导出13k+8有无数个，等量替换，可以推导出X^3有无数个。从而可以得到，这样的X有无数个。。。。

我求出来 2，5，6，15，18，19，28，31，32，41，44，45，54，57，58，67，70，71，80，83....一大堆呢

------解决方案--------------------
C# code

            string input = Console.ReadLine();
            string[] nums = input.Split(' ');

            int x, a, b, c, tempResult;
            List<int> answer = new List<int>();

            //a = Convert.ToInt32(nums[0]);
            a = Convert.ToInt32(nums[0]);
            b = Convert.ToInt32(nums[1]);
            c = Convert.ToInt32(nums[2]);

            for (x = 1; x <= 300; x++)
            {
                tempResult = 1;
                for (int times = 1; times <= a; times++)
                    tempResult *= x;
                if (tempResult % b == c)
                    answer.Add(x);
            }

            answer.ForEach(an => Console.WriteLine(an));