各位佬
我在做NOIP2020T1排水系统
我现在要存一个值为60^11次方的数
longlong存不下现在用double，怎么求gcd
如果不能可以帮我改成int_128吗
代码如下
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN = 100005;
const double mx = (pow(60,11));
#define rep(i,a,b) for(ll i = a;i <= b;i++)
ll n,m,sz[MAXN],x,icnt[MAXN];
double res[MAXN];
vector<int> ed[MAXN];
void read(void){
// freopen("water.in","r",stdin);
// freopen("water.out","w",stdout);
scanf("%lld%lld",&n,&m);
rep(i,1,n){
scanf("%lld",&sz[i]);
rep(j,1,sz[i]){
scanf("%lld",&x);
ed[i].push_back(x);
icnt[x]++;
}
}
}
void dfs(ll x,double q){
// cout << x << " " << mx / q << endl;
if(sz[x] == 0){
res[x] += mx / q;
return;
}
for(auto v : ed[x])dfs(v,q * ed[x].size());
}
ll gcd(ll a,double b){
return (b == 0) ? a : gcd(b,a % b);
}
void solve(){
ll sum = 0;
rep(i,1,n)if(icnt[i] == 0)dfs(i,1),++sum;
rep(i,1,n)res[i] *= sum;
rep(i,1,n)if(sz[i] == 0)printf("%.0lf %.0lf\n",res[i] * 1.0 / gcd(res[i],mx),mx * 1.0 / gcd(res[i],mx));
}
int main(){
read();
solve();
return 0;
}
【以下回答由 GPT 生成】
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN = 100005;
#define rep(i,a,b) for(ll i = a;i <= b;i++)
struct int_128 {
ll high;
ll low;
};
ll gcd(ll a, ll b) {
return b == 0 ? a : gcd(b, a % b);
}
int_128 add(int_128 a, int_128 b) {
int_128 c;
c.low = a.low + b.low;
c.high = a.high + b.high + (c.low < a.low);
return c;
}
int_128 multiply(ll a, ll b) {
int_128 c;
__int128 t = (__int128)a * b;
c.high = t >> 64;
c.low = t;
return c;
}
int_128 divide(int_128 a, ll b) {
int_128 c;
c.high = a.high / b;
c.low = ((a.high % b) << 64) | a.low;
c.low /= b;
return c;
}
int_128 res[MAXN];
ll n, m, sz[MAXN], x, icnt[MAXN];
vector<int> ed[MAXN];
void read() {
// freopen("water.in","r",stdin);
// freopen("water.out","w",stdout);
scanf("%lld%lld", &n, &m);
rep(i,1,n) {
scanf("%lld", &sz[i]);
rep(j,1,sz[i]) {
scanf("%lld", &x);
ed[i].push_back(x);
icnt[x]++;
}
}
}
void dfs(ll x, int_128 q) {
if(sz[x] == 0) {
res[x] = add(res[x], divide(multiply(m, q), gcd(m, q.low)));
return;
}
for(auto v : ed[x]) {
int_128 new_q = multiply(q.low, sz[x]);
dfs(v, new_q);
}
}
void solve() {
ll sum = 0;
rep(i,1,n) {
if(icnt[i] == 0) {
int_128 q;
q.low = 1;
dfs(i, q);
++sum;
}
}
rep(i,1,n) {
res[i] = multiply(res[i].low, sum);
printf("%lld\n", res[i].low);
}
}