P1625 求和 题解

题意

求和

题解

比较好想，小学一年级奥数

可以理解为高精度的大杂烩

代码很简洁，可自行理解

#include<bits/stdc++.h> //万能头 
#define ll long long // 开long long	 
using namespace std;// 命名空间 
ll n,m,a[2005],b[2005],c[4000005];  //a[0],b[0],c[0]分别表示数的长度 
 // 注意a,b,c均是从个位存起！！！！！！！！！！！！！ 
void tms(ll a[],ll x){ //单精度乘法 
	for(ll i=1;i<=a[0];i++)a[i]*=x; //每一位先乘一下 
	for(ll i=1;i<=a[0];i++){ //从个位开始遍历 
		a[i+1]+=a[i]/10; //进位 
		a[i]%=10; // 保留个位 
	} //右大括号 
	while(a[a[0]+1]>0){ //进位如果超过数的长度，长度++ 
		a[0]++; // 长度++ 
		a[a[0]+1]+=a[a[0]]/10; // 进位 
		a[a[0]]%=10; //保留个位 
	} //右大括号 
} //右大括号 
void dvs(ll a[],ll x){ //单精度除法 
	ll tmp=0; //有点像长除法 
	for(ll i=a[0];i>=1;i--){ // 从最高位开始遍历 
		tmp=tmp*10+a[i];  // 加上 
		a[i]=tmp/x; // 除一下，PS：这里可以这么操作如果tmp<x那么a[i]=0 
		tmp%=x; //摸一下 
	} //右大括号 
	while(a[a[0]]==0&&a[0]>0)a[0]--; //长度-- 
} //右大括号 
int main(){ //主函数 
	ios::sync_with_stdio(0); //ios提快 
	cin.tie(nullptr); //ios提快 
	cout.tie(nullptr);  //ios提快 
	cin>>n>>m; // 输入 
	a[0]=a[1]=b[0]=b[1]=c[0]=c[1]=1; //初始化，长度为1，初始数值为1（方便乘） 
	for(ll i=2;i<m;i++)tms(a,i),tms(c,i); //  列项 
	for(ll i=n+1;i<n+m;i++)tms(b,i),tms(c,i);//  列项 
	tms(c,m-1);//  列项 
	//c存的是a*b 
	for(ll i=1;i<=b[0];i++){ //b-=a 高精减 
		b[i]-=a[i]; //减一下 
		if(b[i]<0){ //小于零退位 
			b[i]+=10; //小于零退位 
			b[i+1]--; //小于零退位 
		} //右大括号 
	} //右大括号 
	while(b[0]>0&&b[0]==0)b[0]--; // 退位 
	for(ll j=2;j<n+m;j++){ // 遍历用来约分的数 
		ll x1=0,x2=0; //存模数的 
		for(ll i=b[0];i>=1;i--)x1=(x1*10+b[i])%j; //摸摸 
		for(ll i=c[0];i>=1;i--)x2=(x2*10+c[i])%j; //摸摸 
		while(x1==0&&x2==0){ //如果同时是b-a,c的因数 while!!!!
			dvs(b,j); //除一下 
			dvs(c,j); //除一下 
			for(ll i=b[0];i>=1;i--)x1=(x1*10+b[i])%j; //摸摸 
			for(ll i=c[0];i>=1;i--)x2=(x2*10+c[i])%j; //摸摸 
		} //右大括号 
	} //右大括号 
	for(ll i=b[0];i>=1;i--)cout<<b[i]; //记得倒序输出 
	cout<<"\n"; //换行 
	for(ll i=c[0];i>=1;i--)cout<<c[i]; //记得倒序输出 
	return 0; //好习惯 
} //右大括号

求关注QWQ