2015
02-21

# God of Number Theory

In ACM_DIY, there is one master called “AekdyCoin”. As we know, he is the god of “Number Theory”. He always kills the problem about “Number Theory” in seconds! But of course we do not have any idea about these problems~ One day in ACM_DIY, AekdyCoin asks us one problem:
You are given three non-negative integers A, B and K, you are expected to find how many X that satisfy.
X^A = B( mod (2K + 1) )
X is in the ranger [0, 2K];

Of course we have no idea about this problem, so could you help us?

The first line is one integer T indicates the number of the test cases. (T <= 1000)
Then for every case, only one line contains three integers A, B and K. (1 <= A, B <= 10^9, 1 <= K <= 5 * 10^8)

The first line is one integer T indicates the number of the test cases. (T <= 1000)
Then for every case, only one line contains three integers A, B and K. (1 <= A, B <= 10^9, 1 <= K <= 5 * 10^8)

3

1 1 1
11 11 11
111 111 111

1
0
0

1. 问题3是不是应该为1/4 .因为截取的三段，无论是否能组成三角形， x， y-x ，1-y,都应大于0，所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.

2. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.