結果

問題 No.40 多項式の割り算
コンテスト
ユーザー beet
提出日時 2018-11-12 17:54:57
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 5 ms / 5,000 ms
コード長 2,873 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,350 ms
コンパイル使用メモリ 202,180 KB
最終ジャッジ日時 2025-01-06 16:33:25
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


struct Polynomial{
  using P = Polynomial;
  vector<Int> co;
  Polynomial():co(1,1){}
  Polynomial(Int s):co(s,0){}
  Polynomial(vector<Int> co):co(co){}
  
  size_t size() const{
    return co.size();
  };

  void shrink(){
    while(co.size()>1u&&!co.back())
      co.pop_back();
  }

  void reduce(){
    Int g=abs(co.back());
    if(!g) return;
    for(Int c:co)
      if(c!=0) g=__gcd(g,abs(c));
    if(co.back()<0) g*=-1;
    for(Int &c:co) c/=g;
  }

  void print(){
    shrink();
    reduce();
    Int n=size(),flg=0;
    for(Int i=n-1;i>0;i--){
      if(!co[i]) continue;
      flg=1;
      if(i!=n-1&&co[i]>0) cout<<"+";
      if(co[i]==-1) cout<<"-";
      else if(co[i]!=1) cout<<co[i];
      
      cout<<"x";
      if(i!=1) cout<<"^"<<i;
    }
    if(co[0]){
      if(flg&&co[0]>0) cout<<"+";
      cout<<co[0];
    }
    cout<<endl;
  }

  Int operator[](Int i) const{
    return co[i];
  }

  Int &operator[](Int i){
    return co[i];
  }

  P operator-() const{
    P res=*this;
    for(Int &c:res.co) c*=-1;
    return res;
  }

  P operator+(const P &a) const{
    Int n=size(),m=a.size();
    P res(max(n,m));
    for(Int i=0;i<n;i++) res[i]+=co[i];
    for(Int i=0;i<m;i++) res[i]+=a[i];
    return res;
  }
  P operator-(const P &a) const{return *this+(-a);};

  P operator*(const P &a) const{
    Int n=size(),m=a.size();
    P res(n+m);
    for(Int i=0;i<n;i++)
      for(Int j=0;j<m;j++)
        res[i+j]+=co[i]*a[j];
    res.shrink();
    return res;
  }

  P pow(const P &a,Int k) const{
    P res;
    for(Int i=0;i<k;i++) res=res*a;
    return res;
  }
  
  pair<P, P> divide(const P &a) const{
    Int n=size(),m=a.size(),s=n-m+1;
    if(s<0) return make_pair(P(1),*this);
    P div(s);
    P rest=*this;
    for(Int i=0;i<s;i++){
      if(rest[n-(i+1)]%a[m-1]!=0)
        for(Int &c:rest.co) c*=a[m-1];
      Int d=rest[n-(i+1)]/a[m-1];
      div[s-(i+1)]=d;
      for(Int j=m;j>0;j--) rest[n-(i+j)]-=a[m-j]*d;
    }
    return make_pair(div,rest);
  }
  
  P operator/(const P &a) const{return divide(a).first;};
  P operator%(const P &a) const{return divide(a).second;};  
};

Polynomial gcd(Polynomial a,Polynomial b){
  a.shrink();a.reduce();
  b.shrink();b.reduce();
  if(a.size()<b.size()) swap(a,b);
  if(b.size()==1u&&!b[0]) return a;
  return gcd(b,a%b);
}


//INSERT ABOVE HERE
signed main(){
  Int d;
  cin>>d;
  vector<Int> a(d+1);
  for(Int i=0;i<=d;i++) cin>>a[i];
  vector<Int> b({0,-1,0,1});
  Polynomial x(a),y(b);
  Polynomial z=x%y;
  z.shrink();
  auto co=z.co;
  cout<<co.size()-1<<endl;
  for(Int i=0;i<(Int)co.size();i++){
    if(i) cout<<" ";
    cout<<co[i];
  }
  cout<<endl;
  return 0;
}
0