double可不可以求gcd,如果不能那么怎么改成int_128

Question

各位佬
我在做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;
}

Answer 1

【以下回答由 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);
    }
}

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^