HDU 2685 GCD推导

求$(a^n-1,a^m-1) \mod k$，自己手推，或者直接引用结论$(a^n-1,a^m-1) \equiv a^{(n,m)}-1 \mod k$

/** @Date    : 2017-09-21 21:41:26

  * @FileName: HDU 2685 结论 定理 推导.cpp

  * @Platform: Windows

  * @Author  : Lweleth (SoungEarlf@gmail.com)

  * @Link    : https://github.com/

  * @Version : $Id$

  */

#include <bits/stdc++.h>

#define LL long long

#define PII pair<int ,int>

#define MP(x, y) make_pair((x),(y))

#define fi first

#define se second

#define PB(x) push_back((x))

#define MMG(x) memset((x), -1,sizeof(x))

#define MMF(x) memset((x),0,sizeof(x))

#define MMI(x) memset((x), INF, sizeof(x))

using namespace std;

const int INF = 0x3f3f3f3f;

const int N = 1e5+20;

const double eps = 1e-8;

LL fpow(LL a, LL n, LL mod)

{

	LL res = 1;

	while(n)

	{

		if(n & 1)

			res = res * a % mod;

		a = a * a % mod;

		n >>= 1;

	}

	return res;

}

int main()

{

	int T;

	cin >> T;

	while(T--)

	{

		LL a, m, n, k;

		scanf("%lld%lld%lld%lld", &a, &m, &n, &k);

		printf("%lld\n", (fpow(a,__gcd(m,n),k) - 1 + k) % k);

	}

    return 0;

}

巴特西

HDU 2685 GCD推导

最新文章

热门文章