High-precision

• Core idea: String analog array, large integer (larger than long range) operation.
• Read in:

    void init(int a[])
    {
        string s;
        cin>>s;
        a[0]=s.lenth();
        for(int i=1;i<=a[0];++i)
        a[i]=s[a[0]-i]-'0';
    }

• Carry, borrow processing

Additive carry:

c[i]=a[i]+b[i];
if(c[i]>=10)
{
	c[i]%=10;
	++c[i+1];
}

Subtractive borrowing:

if(a[i]<b[i])
{
	--a[i+1];
	a[i]+=10;
}
c[i]=a[i]-b[i];

Multiplicative carry:

c[i+j-1]=a[i]*b[j]+x+c[i+j-1];
x=c[i+j-1]/10;
c[i+j-1]%=10;

Quotient and Remainder: Depending on the circumstances

• Code

High Precision Addition (Template: A+B problem High Precision)

#include<cstdio>
#include<cstring>
using namespace std;

char a1[505],b1[505];
int len1,len2,len3;
int a[505],b[505],c[505];

int main()
{
	scanf("%s%s",a1,b1);
	len1=strlen(a1);
	len2=strlen(b1);
	for(int i=0;i<len1;++i)
	a[len1-i]=a1[i]-'0';
	for(int i=0;i<len2;++i)
	b[len2-i]=b1[i]-'0';
	len3=1;
	int x=0;
	while(len3<=len1||len3<=len2)
	{
		c[len3]=a[len3]+b[len3]+x;
		x=c[len3]/10;
		c[len3]%=10;
		len3++;		
	}
	c[len3]=x;
	if(c[len3]==0)len3--;
	for(int i=len3;i>=1;--i)
	printf("%d",c[i]);
	return 0;
}

High Precision Subtraction (Template: High Precision Subtraction)

#include<cstdio>
#include<cstring>
#define maxn 10005
using namespace std;

char a1[maxn],b1[maxn],m[maxn];
int len1,len2,len3,flag;
int a[maxn],b[maxn],c[maxn];

int main()
{
	scanf("%s%s",a1,b1);
	if(strlen(a1)<strlen(b1)||(strlen(a1)==strlen(b1)&&strcmp(a1,b1)<0))
	{
		flag=1;
		strcpy(m,a1);
		strcpy(a1,b1);
		strcpy(b1,m);
	}//Commutative array
	len1=strlen(a1);
	len2=strlen(b1);
	for(int i=0;i<len1;++i)a[len1-i]=a1[i]-'0';
	for(int i=0;i<len2;++i)b[len2-i]=b1[i]-'0';
	len3=1;
	int x=0;
	while(len3<=len1||len3<=len2)
	{
		if(a[len3]<b[len3])
		{
			a[len3]+=10;
			a[len3+1]--;
		}//Borrow position
		c[len3]=a[len3]-b[len3];
		len3++;
	}
	while(c[len3]==0&&len3>1)len3--;
	if(len3==1&&c[1]==0)
	{
		printf("0");
		return 0;
	}
	if(flag)
	printf("-");
	for(int i=len3;i>=1;--i)
	printf("%d",c[i]);
	return 0;
}

High Precision Multiplication (Template: A*B problem)

#include<cstdio>
#include<cstring>
#define maxn 5005
using namespace std;

char a1[maxn],b1[maxn];
int len1,len2,len3;
int a[maxn],b[maxn],c[maxn];

int main()
{
	scanf("%s%s",a1,b1);
	len1=strlen(a1);
	len2=strlen(b1);
	for(int i=0;i<len1;++i)a[len1-i]=a1[i]-'0';
	for(int i=0;i<len2;++i)b[len2-i]=b1[i]-'0';
	for(int i=1;i<=len1;++i)
	{
		int x=0;
		for(int j=1;j<=len2;++j)
		{
			c[i+j-1]+=a[i]*b[j]+x;
			x=c[i+j-1]/10;
			c[i+j-1]%=10;
		}
		c[i+len2]=x;
	}
	len3=len1+len2;
	while(c[len3]==0&&len3>1)len3--;
	for(int i=len3;i>=1;--i)
	printf("%d",c[i]);
	return 0;
}

High Precision Division (High Precision Division by Low Precision) (Template: A/B problem)

#include<cstdio>
#include<cstring>
#define maxn 10005
using namespace std;

int len1,len2;
int b,a[maxn],c[maxn];
char a1[maxn];

int main()
{
	scanf("%s%d",a1,&b);
	len1=strlen(a1);
	for(int i=0;i<len1;++i)a[i+1]=a1[i]-'0';
	int x=0;
	for(int i=1;i<=len1;++i)
	{
		c[i]=(x*10+a[i])/b;
		x=(x*10+a[i])%b;
	}
	len2=1;
	while(c[len2]==0&&len2<len1)len2++;
	for(int i=len2;i<=len1;++i)
	printf("%d",c[i]);
	return 0;
}

High Precision Division (High Precision Division by High Precision) (Template: A/B problem II)

#include<cstdio>
#include<cstring>
#include<iostream>
#define maxn 1005
using namespace std;

int a[maxn],b[maxn],c[maxn];

void read(int a[])
{
	string s;
	cin>>s;
	a[0]=s.length();
	for(int i=1;i<=a[0];++i)
	a[i]=s[a[0]-i]-'0';
}//Read in

void print(int a[])
{
	if(a[0]==0)
	{
		printf("0\n");
		return;
	}
	for(int i=a[0];i>0;--i)
	printf("%d",a[i]);
	printf("\n");
	return;
}//output

int cmp(int a[],int b[])
{
	if(a[0]>b[0])return 1;
	if(a[0]<b[0])return -1;
	for(int i=a[0];i>0;--i)
	{
		if(a[i]>b[i])return 1;
		if(a[i]<b[i])return -1;
	}
	return 0;
}//Compare the sizes of arrays a and B

void jian(int a[],int b[])
{
	int flag;
	flag=cmp(a,b);
	if(flag==0)
	{
		a[0]=0;
		return;
	}//Equal
	if(flag==1)
	{
		for(int i=1;i<=a[0];++i)
		{
			if(a[i]<b[i])
			{
				a[i+1]--;
				a[i]+=10;
			}//Borrow position
			a[i]-=b[i];
		}
		while(a[0]>0&&a[a[0]]==0)a[0]--;
		return;
	}
}//Analog subtraction

void numcpy(int p[],int q[],int del)
{
	for(int i=1;i<=p[0];++i)
	q[i+del-1]=p[i];
	q[0]=p[0]+del-1;
}//Array replication

void chugao(int a[],int b[],int c[])
{
	int tmp[maxn];
	c[0]=a[0]-b[0]+1;
	for(int i=c[0];i>=1;--i)
	{
		memset(tmp,0,sizeof(tmp));
		numcpy(b,tmp,i);
		while(cmp(a,tmp)>=0)
		{
			c[i]++;
			jian(a,tmp);
		}	
	}
	while(c[0]>0&&c[c[0]]==0)c[0]--;
	return;
}

int main()
{
	read(a);read(b);
	chugao(a,b,c);
	print(c);
	print(a);//Output Residual
	return 0;
}

Multiplicative Inverse Element

Arrangement and combination

Binomial theorem

Decision and Application of Prime Number

Divisor

Expanding Euclid

Matrix correlation

Fast Multiplication and Fast Power

Euler function

Euler's Theorem and Fermat's Small Theorem

Extended Euler Theorem

Chinese Remainder Theorem

Expanding Chinese Remainder Theorem

Lucas theorem

Expanding Lucas Theorem

Dirichlet convolution

Mobius function

Mobius inversion

Large step and small step algorithm (BSGS)

Extended Big Step and Small Step Algorithms

Du Jiaoxian

Fast Fourier Transform (fft)

Fast number theory transformation (ntt)

* Stirling number correlation algorithm