首页 > 其他分享 >高精度

高精度

时间：2023-11-09 17:22:05浏览次数：37  
标签：BigNumber hz return 高精度 int hp kz 

#include<bits/stdc++.h>
#define N 20005
#define M 40005
#define ll long long
#define a hz.w
#define b kz.w
#define c kzkz.w
#define d kzzf.w
#define hp hz.p
#define kp kz.p
#define cp kzkz.p
#define dp kzzf.p
#define P 998244353
#define inv(x) ksm(x,P-2)
#define zero(x) (x.w[0]==1 && x.w[1]==0)
using namespace std;
char orz[N];
int rev[M],G[2][25],e[M],f[M],ksm(int x,int y);
void NTT(int*g,int t,int s);
struct BigNumber{
	int w[N];bool p=1;
	void set0(){w[0]=1,w[1]=0,p=1;}
	void set1(){w[0]=1,w[1]=1,p=1;}
	void read(){
		scanf("%s",orz);
		w[0]=strlen(orz);
		if(orz[0]=='-'){
			p=0;w[0]--;
			for(int i=1;i<=w[0];i++)w[w[0]-i+1]=orz[i]-'0';
		}
		else{
			p=1;
			for(int i=0;i<w[0];i++)w[w[0]-i]=orz[i]-'0';
		}
	}
}s,t;
BigNumber kz,kzkz,kzzf;
void write(BigNumber kz){
	if(!kz.p)putchar('-');
	for(int i=b[0];i>=1;i--)putchar(b[i]+'0');
	putchar('\n');
}
bool operator>(BigNumber hz,BigNumber kz);
bool operator<(BigNumber hz,BigNumber kz){
	if(hp!=kp)return kp;
	if(!hp){
		hp=kp=1;
		return hz>kz;
	}
	if(a[0]!=b[0])return a[0]<b[0];
	for(int i=a[0];i>=1;i--)
		if(a[i]!=b[i])
			return a[i]<b[i];
	return 0;
}
bool operator>=(BigNumber hz,BigNumber kz);
bool operator<=(BigNumber hz,BigNumber kz){
	if(hp!=kp)return kp;
	if(!hp){
		hp=kp=1;
		return hz>=kz;
	}
	if(a[0]!=b[0])return a[0]<b[0];
	for(int i=a[0];i>=1;i--)
		if(a[i]!=b[i])
			return a[i]<b[i];
	return 1;
}
bool operator>(BigNumber hz,BigNumber kz){
	if(hp!=kp)return hp;
	if(!hp){
		hp=kp=1;
		return hz<kz;
	}
	if(a[0]!=b[0])return a[0]>b[0];
	for(int i=a[0];i>=1;i--)
		if(a[i]!=b[i])
			return a[i]>b[i];
	return 0;
}
bool operator>=(BigNumber hz,BigNumber kz){
	if(hp!=kp)return hp;
	if(!hp){
		hp=kp=1;
		return hz<=kz;
	}
	if(a[0]!=b[0])return a[0]>b[0];
	for(int i=a[0];i>=1;i--)
		if(a[i]!=b[i])
			return a[i]>b[i];
	return 1;
}
bool operator==(BigNumber hz,BigNumber kz){
	if(hp!=kp)return 0;
	if(a[0]!=b[0])return 0;
	for(int i=a[0];i>=1;i--)
		if(a[i]!=b[i])
			return 0;
	return 1;
}
bool operator!=(BigNumber hz,BigNumber kz){
	if(hp!=kp)return 1;
	if(a[0]!=b[0])return 1;
	for(int i=a[0];i>=1;i--)
		if(a[i]!=b[i])
			return 1;
	return 0;
}
BigNumber operator-(BigNumber hz,BigNumber kz);
BigNumber operator+(BigNumber hz,BigNumber kz){
	if(zero(hz))return kz;
	if(zero(kz))return hz;
	if(hp!=kp){
		if(!kp)return kp=!kp,hz-kz;
		return hp=!hp,kz-hz;
	}
	int ws=max(a[0],b[0]),jw=0;
	for(int i=1;i<=ws;i++){
		if(a[0]<i)a[i]=0;
		if(b[0]<i)b[i]=0;
		b[i]=b[i]+a[i]+jw;
		jw=b[i]/10;
		b[i]%=10;
	}
	while(jw){
		ws++;
		b[ws]=jw%10;
		jw/=10;
	}
	b[0]=ws;
	if(zero(kz))kp=1;
	return kz;
}
BigNumber operator-(BigNumber hz,BigNumber kz){
	if(zero(kz))return hz;
	if(zero(hz)){
		kp=!kp;
		return kz;
	}
	if(!hp&&kp){
		kp=!kp;
		return hz+kz;
	}
	if(hp&&!kp){
		kp=!kp;
		return hz+kz;
	}
	if(!hp&&!kp){
		hp=!hp,kp=!kp;
		swap(hz,kz);
	}
	bool gk=1;
	if(hz<kz){
		gk=0;
		swap(hz,kz);
	}
	int ws=max(a[0],b[0]);
	for(int i=1;i<=ws;i++){
		if(i>b[0])b[i]=a[i];
		else b[i]=a[i]-b[i];
		if(b[i]<0){
			b[i]+=10;
			a[i+1]--;
		}
	}
	while(!b[ws]&&ws>1)ws--;
	b[0]=ws;
	if(!gk)kp=!kp;
	if(zero(kz))kp=1;
	return kz;
}
BigNumber operator*(BigNumber hz,BigNumber kz){
	if(zero(hz)||zero(kz)){
		hz.set0();
		return hz;
	}
	hp=!(hp^kp);
	int la=a[0],lb=b[0],s=1,l=0;
	while(s<la+lb)s<<=1,l++;
	rev[0]=0;
	for (int i=1;i<s;i++)
		rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
	e[0]=f[0]=0;
	for(int i=1;i<=la;i++)e[i-1]=a[i];
	for(int i=1;i<=lb;i++)f[i-1]=b[i];
	for(int i=la;i<s;i++)e[i]=0;
	for(int i=lb;i<s;i++)f[i]=0;
	NTT(e,0,s),NTT(f,0,s);
	for (int i=0;i<s;i++)e[i]=(ll)e[i]*f[i]%P;
	NTT(e,1,s);
	int invs=inv(s);
	for(int i=s;i>=1;i--)e[i]=(ll)e[i-1]*invs%P;
	e[0]=0;
	for(int i=1;i<=la+lb;i++){
		e[i+1]+=e[i]/10;
		e[i]%=10;
	}
	a[0]=la+lb;
	while(!e[a[0]]&&a[0]>1)a[0]--;
	for(int i=1;i<=a[0];i++)a[i]=e[i];
	return hz;
}
BigNumber operator/(BigNumber hz,BigNumber kz){
	if(zero(hz)){
		kzkz.set0();
		return kzkz;
	}
	if(hp!=kp)cp=0;
	else cp=1;
	hp=kp=1;
	for(int i=0;i<=a[0];i++)c[i]=d[i]=0;
	d[0]=1;
	for(int i=a[0];i>=1;i--){
		if(d[0]!=1||d[1]){
			for(int i=d[0];i>=1;i--)d[i+1]=d[i];
			d[1]=a[i];d[0]++;
		}
		else d[1]=a[i];
		while(kzzf>=kz)kzzf=kzzf-kz,c[i]++;
	}
	c[0]=a[0];
	while(!c[c[0]]&&c[0]>1)c[0]--;
	if(zero(kzkz))cp=1;
	return kzkz;
}
BigNumber operator%(BigNumber hz,BigNumber kz){
	if(zero(hz)){
		kzzf.set0();
		return kzzf;
	}
	bool gk;
	gk=hp,hp=kp=1;
	for(int i=0;i<=a[0];i++)d[i]=0;
	d[0]=1;
	for (int i=a[0];i>=1;i--){
		if(d[0]!=1||d[1]){
			for(int i=d[0];i>=1;i--)d[i+1]=d[i];
			d[1]=a[i],d[0]++;
		}
		else d[1]=a[i];
		while(kzzf>=kz)kzzf=kzzf-kz;
	}
	dp=gk;
	if(zero(kzzf))dp=1;
	return kzzf;
}
void operator+=(BigNumber&kz,BigNumber hz){kz=kz+hz;}
void operator-=(BigNumber&kz,BigNumber hz){kz=kz-hz;}
void operator*=(BigNumber&kz,BigNumber hz){kz=kz*hz;}
void operator/=(BigNumber&kz,BigNumber hz){kz=kz/hz;}
void operator%=(BigNumber&kz,BigNumber hz){kz=kz%hz;}
BigNumber Number_Turn_BigNumber(ll x){
	if(x==0){
		kz.set0(),kp=1;
		return kz;
	}
	if(x<0){
		kp=0;
		x=-x;
	}else kp=1;
	b[0]=0;
	while(x){
		b[++b[0]]=x%10;
		x/=10;
	}
	return kz;
}
ll BigNumber_Turn_Number(BigNumber kz){
	ll y=0;
	for(int i=b[0];i>=1;i--)y=y*10+b[i];
	if(!kp)y=-y;
	return y;
}
void NTT(int*q,int t,int s){
	for(int i=0;i<s;i++)if(i<rev[i])swap(q[i],q[rev[i]]);
	for(int mid=1,o=1;mid<s;mid<<=1,o++)
		for(int j=0;j<s;j+=(mid<<1)){
			int g=1;
			for(int k=0;k<mid;k++,g=(ll)g*G[t][o]%P){
				int x=q[j+k],y=(ll)g*q[j+k+mid]%P;
				q[j+k]=(x+y)%P;
				q[j+k+mid]=(x-y+P)%P;
			}
		}
}
int ksm(int x,int y){
	int ans=1;
	while(y){
		if(y&1)ans=(ll)ans*x%P;
		x=(ll)x*x%P,y>>=1;
	}
	return ans;
}
void Pre(){
	G[0][23]=ksm(3,(P-1)/(1<<23));
	G[1][23]=inv(G[0][23]);
	for(int i=22;i>=1;i--){
		G[0][i]=(ll)G[0][i+1]*G[0][i+1]%P;
		G[1][i]=(ll)G[1][i+1]*G[1][i+1]%P;
	}
}
#undef a
#undef b
#undef c
#undef d
#undef hp
#undef kp
#undef cp
#undef dp
int main(){
	Pre();
	s.read(),t.read();
	write(s+t);
	write(s-t);
	write(s*t);
	write(s/t);
	write(s%t);
	return 0;
}

标签：BigNumber,hz,return,高精度,int,hp,kz
From： https://www.cnblogs.com/2021changqing52/p/17822356.html

相关文章

  • 三坐标测量机轮廓度测量操作指南：打造高精度测量解决方案
    在现代制造业中，精确度和质量控制是至关重要的因素。而对于产品的尺寸和形状的测量，三坐标测量机成为了一种重要工具。一、为什么选择三坐标测量机？三坐标测量机是一种能够精确测量物体三维尺寸和形状的设备。相较于传统的测量工具，三坐标测量机具有以下优势：高精度：三坐标测量机采用先......
  • 高精度减法（C语言实现）
    高精度减法（C语言实现）介绍众所周知，整数在C和C++中以int，long，longlong三种不同大小的数据存储，数据大小最大可达2^64，但是在实际使用中，我们仍不可避免的会遇到爆longlong的超大数运算，这个时候，就需要我们使用高精度算法，来实现巨大数的运算。高精度的本质是将数字以字符串的形式......
  • 高精度加法（C语言实现）
    高精度加法（C语言实现）介绍众所周知，整数在C和C++中以int，long，longlong三种不同大小的数据存储，数据大小最大可达2^64，但是在实际使用中，我们仍不可避免的会遇到爆longlong的超大数运算，这个时候，就需要我们使用高精度算法，来实现巨大数的运算。高精度的本质是将数字以字符串的形式......
  • 用c++写一个高精度计算的除法运算
    高精度除以低精度以下这段代码的主要作用是将一个大整数（以字符数组形式表示）除以一个整数，并输出结果。具体来说，代码将大整数a1（“1256”）除以整数b（3），并输出商。#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;intmain(){chara1[100]="1256";......
  • 蓝牙信道探测（Channel Sounding）: 高精度距离测量
    https://mp.weixin.qq.com/s/2V9NfRvyuLRwVph7nzA3ng 信道探测（Channel Sounding） CS引入了79个物理信道，CS使用不同信道的接收和发送信号之间的相移以及RTT(往返时间)测量来进行距离估算并相互修正，精度更高。 ​BLECS提供一种相位测距（PBR：phase‑basedranging）方案，主要......
  • 高精度（加减乘除）
    高精度（加减乘除）高精度的核心思想就是利用数组去储存大数，然后通过模拟手动计算的方式，来进行计算。主要分三个模块：1.读入数据并转换为(int)类型储存高精度加法核心思想：将每个位上的数字都＋起来，如果大于10就进位。核心代码如下：c[i]+=a[i]+b[i];//两数相加c[i+1]+=c[i]/10;//进......
  • 高精度加减乘除
    大整数的高精度运算加法#include<bits/stdc++.h>usingnamespacestd;vector<int>big_num_add(vector<int>n1,vector<int>n2){vector<int>ans;intt=0;for(inti=0;i<n1.size()||i<n2.size();i++){if(i&l......
  • 高精度除法
    一、算法描述高精度除法和乘法讨论的一样，都是一个大整数和一个小整数之间的运算。算法思路根据小学除法一样，我们还是模拟这个过程。注意这里遍历\(A\)数组的时候要按照我们读数字的顺序，也就是从数组尾部到头部遍历。每一位的计算过程应该是，上一轮的余数\(r\)乘\(10\)之......
  • RTK高精度定位安全帽-UWB室内定位/GPS定位智能安全帽技术方案
    高精度RTK定位安全帽是一种综合性解决方案，结合了先进的GPS定位技术、物联网技术、移动数据传输和智能执法管理。相较于传统的定位安全帽，它提供了更高的定位精度、更强大的数据处理能力和更全面的施工过程记录，对公共安全领域有着实质性的积极影响。该安全帽采用厘米级RTK定......
  • 高精度乘法
    一、算法描述高精度加减法讨论的是两个大整数之间的运算。而这里高精度乘除法讨论的是一个大整数和一个小整数之间的关系。算法思路：还是模拟小学的乘法列竖式，只不过此时不太一样，原本的列竖式是一位一位的乘，这里需要改变一下思路。这里直接把小整数当成一个数，所乘的数直接......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99