题目链接：

题意：求gcd(a^m - 1, a^n - 1) mod k

思路：gcd(a^m - 1, a^n - 1) = a^gcd(m, n) - 1

code：

1 #include 
     
       2  3 int gcd(int a, int b) 4 { 5     return !b ? a : gcd(b, a%b); 6 } 7  8 int mod_pow(int a, int x, int mod) 9 {10     int tmp = a;11     int ret = 1;12     while(x) {13         if (x & 1) {14             ret = ret * tmp % mod;15         }16         tmp = tmp * tmp % mod;17         x >>= 1;18     }19 20     return ret;21 }22 23 int main()24 {25     int t, a, m, n, k;26     scanf("%d", &t);27     while (t--) {28         scanf("%d %d %d %d", &a, &m, &n, &k);29         int d = gcd(m, n);30         int ans = mod_pow(a, d, k);31         printf("%d\n", (ans - 1 + k) % k); 32     }33 34     return 0;35 }