70 分求调
查看原帖
70 分求调
514727
bcdmwSjy楼主2025/1/2 10:18

TLE 先不说,为什么 WA 两个点啊

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 i128;

const ll mod=9000000114000000377;

int n,m,c;

pair<i128,i128> calc(i128 p,i128 q,i128 A){
    i128 x=q,y=p,a=1,b=0;
    while (x>A){
        swap(x,y);
        swap(a,b);
        a-=x/y*b;
		x%=y;
    }
    return {x,a};
}

i128 inv(i128 x){
	if (x<=1) return 1;
	return i128(mod-mod/x)*inv(mod%x)%mod;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>c;
	i128 a=1;
	while (n--){
		ll x;
		cin>>x;
		a=a*x%mod;
	}
	while (m--){
		ll x;
		cin>>x;
		a=a*inv(x)%mod;
	}
	auto [u,v]=calc(mod,a,3000000019);
	i128 g=__gcd(u,v);
	cout<<ll(u/g)<<" "<<ll(v/g);
	return 0;
}
2025/1/2 10:18
加载中...