C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 480K, 提交时间: 2019-10-31 14:50:40

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#define oo 0x3ffff
#define Mod 20190930
#define ll long long
using namespace std;

int T;

ll exgcd(ll a,ll b,ll &x1,ll &y1)
{
	if(b == 0) {x1 = 1,y1 = 0;return a;}
	ll d = exgcd(b,a % b,x1,y1);
	ll z = x1;x1 = y1;y1 = z - y1 * (a / b);
	return d;
}

ll ksm(ll a,ll b)
{
	ll ans = 1;
	a = a % Mod;
	while(b){
		if(b & 1) ans = ans * a % Mod;
		b = b / 2;
		a = (a * a) % Mod;
	}
	return ans;
}

int main()
{
	ll a,b,c,d,x1,y1;
	scanf("%d",&T);
	while(T--){
		scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
		ll x = ksm(a,b);
		ll y = ksm(c,d);
		ll tmp = exgcd(y,Mod,x1,y1);
		ll y2 = ( (x1 % Mod + Mod) % Mod ) / tmp;
		ll Ans = x * y2 % Mod;
		printf("%lld\n",Ans);
	}
	return 0;
}

Python3 解法, 执行用时: 41ms, 内存消耗: 5140K, 提交时间: 2022-08-15 23:47:23

P=20190930
def power(a,b):
    ans=1%P
    while b>=1:
        if b%2==1:
            ans=ans*a%P
        a=a*a%P
        b=b//2
    return ans

def exgcd(a, b):     
    if b == 0:         
        return 1, 0, a     
    else:         
        x, y, q = exgcd(b, a % b)        
        x, y = y, (x - (a // b) * y)         
        return x, y, q

t=int(input())
while t>0 :
    a,b,c,d = map(int,input().split())
    x,y,q=exgcd(c,P)
    c=(x%P+P)%P
    print(power(a,b)*power(c,d)%P)
    t=t-1

C++(clang++ 11.0.1) 解法, 执行用时: 3ms, 内存消耗: 424K, 提交时间: 2023-06-27 20:09:47

#include<bits/stdc++.h>
using namespace std;
const int P = 20190930;
int64_t powMod(int64_t a, int64_t b, int64_t p) {
  a %= p;
  int64_t s = 1;
  while (b) {
    if (b % 2) s = s * a % p;
    b /= 2, a = a * a % p;
  }
  return s;
}
int64_t inv(int64_t a, int64_t b){
 return 1<a ? b - inv(b%a,a)*b/a : 1;
}

int main(){
  int T; cin >> T;
  while (T--) {
    int a, b, c, d; cin >> a >> b >> c >> d;
    cout << powMod(a, b, P) * powMod(inv(c, P), d, P) % P << endl;
  }
}