CSP-J模拟T3细节实现

经验分享区
1

CSP-J模拟T3实现

相信大家都知道思路，但具体实现并不好写，所以这篇我就讲讲细节吧

读入就是看你功底了，不再赘述。

首先就是大除法的问题，其实可以不用真的模拟大除法，我们知道如果一个多项式 a_0+a_1x+a_2x^2+... 存在一个因式 (x+d)

那么就可以把这个多项式写成 (x+d)·b_0+(x+d)·b_1x+(x+d)·b_2x^2+...

展开等于 d·b_0+(b_0+d·b_1)·x+(b_1+d·b_2)·x^2+...

对比一下 a_0~~~~~+a_1~~~~~~~~~~~~~~~~·x+a_2~~~~~~~~~~~~~~~~·x^2+...

我们可以从一次项开始，每次减去 b_{i-1} ，也就是减去 a_{i-1}/d , 然后再让前一项 除以 d ，这样我们就得到 b_0+b_1x+b_2x^2... 这个式子了，然后重复执行此流程知道只到这个式子为 1 。

看下实现：

void solve(int d){
	for(int i=1;i<=40;i++){
		x_i[i]-=x_i[i-1]/d;
		x_i[i-1]/=d;
	}
}

没错就是这么简单。

存根建议用 map,不仅好遍历，而且可以存负根

具体实现

我为了展示特意把代码写简洁易懂，但不要拿我的交！！，也不要抄袭！！

#include<bits/stdc++.h>
#define IT map<int,int>::iterator
using namespace std;
const int inf=1e9;
const int M=1145141910;
int f=1,x=0,x_i[50],xishu;
map<int,int> mp;
string s;
inline int bp(int a,int b) {//没必要 
  if (b==0) return 1;
  int res = bp(a,b/2);
  if (b % 2) return(res*res)%M*a%M;
  else return (res*res)%M; 
}
int getw(int w){//多项式求值 
	int res=0;
	for(int i=1;i<=21;i++) res+=x_i[i]*((i&1&&w<0)?-bp(abs(w),i):bp(abs(w),i));
	return res+x_i[0];
}
void solve(int l){//处理根 
	for(int i=1;i<=40;i++){
		x_i[i]-=x_i[i-1]/l;
		x_i[i-1]/=l;
	}
}
int main(){
	cin>>s;
	//字符串处理就不多说了吧，做出这题的前提
	while(x_i[0]!=1||x_i[1]!=0){//不为1就能提因式
		for(int i=1;i<=abs(x_i[0]);i++){
			if(abs(x_i[0])%i==0){
				if(getw(i)==0) {//判根 
					mp[-i]++;solve(-i);
				}
				if(getw(-i)==0){//判根 
					mp[i]++;solve(i);
				}
			}
		}
	}		
	for(IT it=mp.begin(); it != mp.end(); ++it){//输出 
		cout<<"(x"; 
		if(it->first>0) cout<<"+"<<it->first;
		else cout<<it->first;
		cout<<")";
		if(it->second>1) cout<<"^"<<it->second;
	}
	return 0;
}
2 个赞