关于 long double 和 __int128
查看原帖
关于 long double 和 __int128
261046
Cht_master楼主2021/9/5 20:34

rt,两份代码,区别仅在于一个用的是 long double 一个是 __int128 。第一份 80pts ,第二份 AC 。

但是话说 long double 不是可以存到 1030810^{308} 吗?

//80pts,long double.
#include<bits/stdc++.h>
#define db long double
using namespace std;
db GCD(db a,db b){
	if(a<b)swap(a,b);
	if(b==0)return a;
	db l(0),r(a/b+1),k;
	while(l<=r){
		db mid(floor((l+r)/2));
		if(b*mid<=a)k=mid,l=mid+1;
		else r=mid-1;
	}
	return GCD(b,a-k*b);
	//GCD(b,a%b)=GCD(b,a-(a/b)*b).
}
const int mxN(1e5);
int n,m,in[mxN+5],out[mxN+5];
vector<int>nd[mxN+5];
struct Val{db p,q;}val[mxN+5];//1/1 or 0/1.
void add(int u,int v){nd[u].push_back(v),++in[v],++out[u];}
void pls(int u,int v){//结点v加上结点u.
	if(val[u].q==0)return;
	db LCM(val[u].q*val[v].q/GCD(val[u].q,val[v].q)),P,Q;
	P=(val[v].p*(LCM/val[v].q)+val[u].p*(LCM/val[u].q)),Q=LCM;
	db gcd=GCD(P,Q);
	P/=gcd,Q/=gcd,val[v].p=P,val[v].q=Q;
}
void DAG(){
	queue<int>q;
	for(int u(1);u<=n;++u)if(!in[u])q.push(u),val[u].p=val[u].q=1;else val[u].p=0,val[u].q=1;
	while(!q.empty()){
		int u(q.front());q.pop();
		if(nd[u].size()!=0){
			val[u].q*=(db)nd[u].size();
			db gcd(GCD(val[u].p,val[u].q));
			val[u].p/=gcd,val[u].q/=gcd;
		}
		for(int i(0);i<nd[u].size();++i){
			int v(nd[u][i]);pls(u,v);
			if(!(--in[v]))q.push(v);
		}
	}
}
int main(){
//	freopen("water3.in","r",stdin);
//	freopen("me.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int u(1),s;u<=n;++u){
		scanf("%d",&s);
		for(int i(1),v;i<=s;++i)scanf("%d",&v),add(u,v);
	}
	DAG();
	for(int u(1);u<=n;++u)if(!out[u])printf("%.0Lf %.0Lf\n",val[u].p,val[u].q);
	return 0;
}
//100pts,__int128.
#include<bits/stdc++.h>
#define intll __int128
using namespace std;
intll GCD(intll a,intll b){
	if(a<b)swap(a,b);
	if(b==0)return a;
	intll l(0),r(a/b+1),k;
	while(l<=r){
		intll mid(((l+r)/2));
		if(b*mid<=a)k=mid,l=mid+1;
		else r=mid-1;
	}
	return GCD(b,a-k*b);
	//GCD(b,a%b)=GCD(b,a-(a/b)*b).
}
void print(intll x){if(x>9)print(x/10);putchar(x%10+48);}

const int mxN(1e5);
int n,m,in[mxN+5],out[mxN+5];
vector<int>nd[mxN+5];
struct Val{intll w1,w2;}val[mxN+5];//1/1 or 0/1.
void add(int u,int v){nd[u].push_back(v),++in[v],++out[u];}
void pls(int u,int v,intll x){//结点v加上结点u的1/x.
	intll wu1(val[u].w1),wu2(val[u].w2),wv1(val[v].w1),wv2(val[v].w2),gcd;
	gcd=(GCD(wu1,x)),wu1/=gcd,x/=gcd,
	wu2*=x;
	val[v].w1=wu1*wv2+wu2*wv1,val[v].w2=wu2*wv2;
	gcd=GCD(val[v].w1,val[v].w2);
	val[v].w1/=gcd,val[v].w2/=gcd;
}
void DAG(){
	queue<int>q;
	for(int u(1);u<=n;++u)if(!in[u])q.push(u),val[u].w1=val[u].w2=1;else val[u].w1=0,val[u].w2=1;
	while(!q.empty()){
		int u(q.front());q.pop();
		for(int i(0);i<nd[u].size();++i){
			int v(nd[u][i]);
			pls(u,v,1.0*nd[u].size());
			if(!(--in[v]))q.push(v);
		}
	}
}
int main(){
//	freopen("water3.in","r",stdin);
//	freopen("me.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int u(1),s;u<=n;++u){
		scanf("%d",&s);
		for(int i(1),v;i<=s;++i)scanf("%d",&v),add(u,v);
	}
	DAG();
	for(int u(1);u<=n;++u)if(!out[u])print(val[u].w1),putchar(' '),print(val[u].w2),putchar('\n');
	return 0;
}

Tips:

//本地测 long double 范围的代码
#include<bits/stdc++.h>
using namespace std;
int main(){
  long double a;
  a=1e308,cout<<a<<endl;
  a=1e309,cout<<a<<endl;
 	return 0;
}
/*
output:
1e+308
inf
*/
2021/9/5 20:34
加载中...