#P12694. BZOJ2219 数论之神

BZOJ2219 数论之神

题目描述

对于给定的 33 个非负整数 A,B,KA,B,K,求出满足:

  • XAB(mod(2×K+1))X^A \equiv B \pmod{(2\times K + 1)}
  • XX 在范围 [0,2K][0, 2K]

XX 的个数。

输入格式

第一行有一个正整数 TT,表示接下来的数据的组数(T1000T \leq 1000)。之后对于每组数据,给出了 33 个整数 A,B,KA, B, K1A,B1091 \leq A, B \leq 10^9, 1K5×1081 \leq K \leq 5 \times 10^8

输出格式

输出一行,表示答案。

3
213 46290770 80175784
3 46290770 80175784
3333 46290770 80175784

27
27
297