Description:

To think of a beautiful problem description is so hard for me that let’s just drop them off. ?
Given four integers a,m,n,k,and S = g c d ( a m − 1 , a n − 1 ) S = gcd(a^{m}-1,a^{n}-1)%k S=gcd(am−1,an−1),calculate the S.

Input:

The first line contain a t,then t cases followed.
Each case contain four integers a,m,n,k( 1 ≤ a , m , n , k ≤ 10000 1\le a,m,n,k\le10000 1≤a,m,n,k≤10000).

Output:

S

Sample Input:

1
1 1 1 1

Sample Output:

0

题目链接

这道题主要用一个数学定理解决

设 a > b a>b a>b , g c d ( a , b ) = 1 gcd(a,b)=1 gcd(a,b)=1
那么 g c d ( a m − b m , a n − b n ) = a g c d ( m , n ) − b g c d ( m , n ) gcd(a^{m}-b^{m},a^{n}-b^{n})=a^{gcd(m,n)}-b^{gcd(m,n)} gcd(am−bm,an−bn)=agcd(m,n)−bgcd(m,n)

因为题目数据比较大，需要进行快速幂取模运算。
a % k a\%k a%k 如果结果大于零，那么 ( a − 1 ) % k = a % k − 1 (a-1)\%k=a\%k-1 (a−1)%k=a%k−1，如果 a % k = 0 a\%k=0 a%k=0，那么 ( a − 1 ) % k = k − 1 (a-1)\%k=k-1 (a−1)%k=k−1。

AC代码：

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <cctype>
#include <cmath>

using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;

ll gcd(ll x,ll y) {
    return y ? gcd(y,x % y) : x;
}

ll Quick(ll a,ll b,ll c) {
    ll ans = 1;
    a = a % c;
    while (b != 0) {
        if (b & 1) {
            ans = (ans * a) % c;
        }
        b >>= 1;
        a = (a * a) % c;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(0);
    int t;
    cin >> t;
    while (t--) {
        ll a,m,n,k;
        cin >> a >> m >> n >> k;
        ll S;
        S = Quick(a, gcd(m, n), k);
        if (S > 0) {
            S--;
        }
        else if (S == 0) {
            S = k - 1;
        }
        cout << S << endl;
    }
    return 0;
}