求救,不会用__int128
  • 板块灌水区
  • 楼主NightTide
  • 当前回复8
  • 已保存回复8
  • 发布时间2021/8/16 17:27
  • 上次更新2023/11/4 10:27:36
查看原帖
求救,不会用__int128
547908
NightTide楼主2021/8/16 17:27

求助各位大佬,__int128怎么用,有什么要注意的吗。

如果可以的话,举个拿我这份代码举个例子怎么改好吗,谢谢了

#include<bits/stdc++.h>
using namespace std;
struct edge{
    unsigned long long pre;
    unsigned long long to;
};
struct fenshu{
    unsigned long long den;//分母
    unsigned long long mol;//分子
};
edge e[2000010];
unsigned long long head[100010],num[100010],cnt;
unsigned long long n,m;
unsigned long long fina[100010],cnt_zero;
bool vis[100010];
fenshu water[100010],ans[1000010];
void add(unsigned long long u,unsigned long long v){
    e[++cnt].pre=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}
unsigned long long gcd(unsigned long long a,unsigned long long b){
    return b==0 ? a : gcd(b,a%b);
}
void cal(unsigned long long a,unsigned long long b){
    water[a].mol=water[a].mol*water[b].den*num[b]+water[a].den*water[b].mol;
    water[a].den*=water[b].den*num[b];
    unsigned long long g=gcd(water[a].den,water[a].mol);
    water[a].den/=g;water[a].mol/=g;
}
void bfs(unsigned long long start){
    queue<unsigned long long> s;
    s.push(start);
    while(s.size()){
        unsigned long long p=s.front();
        s.pop();
        for(unsigned long long i=head[p];i;i=e[i].pre){
            cal(e[i].to,p);
            s.push(e[i].to);
        }
        if(num[p]){
            water[p].den=1;
            water[p].mol=0;
        }
    }
}
int main(){
    scanf("%lld%lld",&n,&m);
    for(unsigned long long i=1;i<=n;i++){
        scanf("%lld",&num[i]);
        water[i].den=1;ans[i].den=1;
        if(num[i]==0) fina[cnt_zero++]=i;
        for(unsigned long long j=0,a;j<num[i];j++){
            scanf("%lld",&a);
            add(i,a);
        }
    }
    for(unsigned long long i=1;i<=m;i++){
        water[i].den=water[i].mol=1;
    }
    for(unsigned long long i=1;i<=m;i++){
        bfs(i);
    }
    for(unsigned long long i=0;i<cnt_zero;i++){
        unsigned long long g=gcd(water[fina[i]].mol,water[fina[i]].den);
        printf("%lld %lld\n",water[fina[i]].mol/g,water[fina[i]].den/g);
    }
    return 0;
}
2021/8/16 17:27
加载中...