QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#32609 | #885. Keep Calm And Carry Off | Froggygua | AC ✓ | 73ms | 40108kb | C++17 | 10.0kb | 2022-05-22 11:56:20 | 2022-05-22 11:56:21 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
enum multiply_tag{
brute_tag,fft_tag,mix_tag
};
struct Complex{
double x,y;
Complex(double _x=0,double _y=0){x=_x,y=_y;}
friend Complex operator + (const Complex &a,const Complex &b){
return Complex(a.x+b.x,a.y+b.y);
}
friend Complex operator - (const Complex &a,const Complex &b){
return Complex(a.x-b.x,a.y-b.y);
}
friend Complex operator * (const Complex &a,const Complex &b){
return Complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);
}
};
template<int L>
class Poly_fft{
using poly=Poly_fft<L>;
static constexpr double PI=acos(-1.0);
vector<Complex> f;
struct initializer{
vector<Complex> GG[2][L+1];
initializer(){
for(int p=1;p<=L;++p){
Complex buf1(cos(2*PI/(1<<p)),sin(2*PI/(1<<p)));
Complex buf0(cos(2*PI/(1<<p)),-sin(2*PI/(1<<p)));
GG[0][p].resize(1<<p);
GG[1][p].resize(1<<p);
GG[0][p][0]=GG[1][p][0]=Complex(1,0);
for(int i=1;i<(1<<p);++i){
GG[0][p][i]=GG[0][p][i-1]*buf0;
GG[1][p][i]=GG[1][p][i-1]*buf1;
}
}
}
};
static initializer init;
static vector<int> tr;
static int FFT_init(int n){
int lim=1;
while(lim<n)lim<<=1;
tr.resize(lim);
for(int i=0;i<lim;++i){
tr[i]=((tr[i>>1]>>1)|(i&1?lim>>1:0));
}
return lim;
}
static void FFT(poly &A,int flag,int n){
A.resize(n);
for(int i=0;i<n;++i){
if(i<tr[i])swap(A.f[i],A.f[tr[i]]);
}
for(int p=2,j=1;p<=n;p<<=1,++j){
int len=p>>1;
for(int k=0;k<n;k+=p){
auto buf=init.GG[flag][j].begin();
for(int i=k;i<k+len;++i,++buf){
Complex tmp=(*buf)*A.f[i+len];
A.f[i+len]=A.f[i]-tmp;
A.f[i]=A.f[i]+tmp;
}
}
}
if(!flag){
for(int i=0;i<n;++i){
A.f[i].x=A.f[i].x/n;
}
}
}
public:
Poly_fft(const vector<Complex> &_f):f(_f){}
Poly_fft(){}
Poly_fft(int _n){f.resize(_n);}
int size(){return f.size();}
void resize(int _n){f.resize(_n);}
vector<Complex>::reference operator [] (int x){
return f[x];
}
friend poly Mul(poly A,poly B){
int n=A.size()+B.size()-1;
int lim=FFT_init(n);
poly C(lim);
FFT(A,1,lim),FFT(B,1,lim);
for(int i=0;i<lim;++i){
C[i]=A[i]*B[i];
}
FFT(C,0,lim);
C.resize(n);
return C;
}
};
template<int L>
typename Poly_fft<L>::initializer Poly_fft<L>::init;
template<int L>
vector<int> Poly_fft<L>::tr;
using poly=Poly_fft<20>;
/*
进制,压位长度,乘法方式
*/
template<int H,int D,multiply_tag mtag>
class unsigned_bigint{
using bint=unsigned_bigint<H,D,mtag>;
static constexpr int B=round(pow(H,D));
vector<int> g;
public:
unsigned_bigint(const vector<int> &_g):g(_g){}
unsigned_bigint(int x=0){
if(!x){g.resize(1);return;}
while(x)g.push_back(x%B),x/=B;
}
unsigned_bigint(string s){
g.resize(((int)s.length()+D-1)/D);
reverse(s.begin(),s.end());
for(int i=0;i*D<(int)s.length();++i){
for(int j=min(D,(int)s.length()-i*D)-1;j>=0;--j){
g[i]=g[i]*H+s[i*D+j]-'0';
}
}
}
int length(){
int len=D*(g.size()-1);
int x=g.back();
while(x)x/=H,++len;
return max(1,len);
}
void Del(){
g.pop_back();
if(g.empty())g.push_back(0);
}
bint &operator += (const bint &b){
if(b.g.size()>g.size())g.resize(b.g.size());
g.push_back(0);
for(int i=0;i<(int)g.size();++i){
if(i<(int)b.g.size())g[i]+=b.g[i];
if(g[i]>=B)++g[i+1],g[i]-=B;
}
while(g.size()>1&&!g.back())g.pop_back();
return *this;
}
bint &operator -= (const bint &b){
if(b.g.size()>g.size())g.resize(b.g.size());
g.push_back(0);
for(int i=0;i<(int)g.size();++i){
if(i<(int)b.g.size())g[i]-=b.g[i];
if(g[i]<0)--g[i+1],g[i]+=B;
}
while(g.size()>1&&!g.back())g.pop_back();
return *this;
}
bint &operator *= (const bint &b){
vector<ll> tmp;
if(mtag==brute_tag||(mtag==mix_tag&&1LL*g.size()*b.g.size()<=1e7)){
tmp.resize(g.size()+b.g.size());
for(int i=0;i<(int)g.size();++i){
for(int j=0;j<(int)b.g.size();++j){
tmp[i+j]+=1LL*g[i]*b.g[j];
}
}
g.resize(g.size()+b.g.size());
}
else{
poly F(g.size()),G(b.g.size());
for(int i=0;i<(int)F.size();++i)F[i].x=g[i];
for(int i=0;i<(int)G.size();++i)G[i].x=b.g[i];
F=Mul(F,G);
g.resize(F.size()+1);
tmp.resize(F.size()+1);
for(int i=0;i<(int)F.size();++i){
tmp[i]=round(F[i].x);
}
}
for(int i=0;i<(int)tmp.size();++i){
g[i]=tmp[i]%B;
if(tmp[i]>=B)tmp[i+1]+=tmp[i]/B;
}
while(g.size()>1&&!g.back())g.pop_back();
return *this;
}
bint &operator /= (const bint &b){
if(b.g.size()>g.size()){
g=vector<int>(1);
}
else{
bint a;
a.g.resize(g.size()-b.g.size()+1);
for(int i=g.size()-b.g.size();i>=0;--i){
bint tmp(vector<int>(g.begin()+i,g.end()));
g.erase(g.begin()+i,g.end());
int l=0,r=B;
while(l<r){
int mid=(l+r)>>1;
if(bint(mid)*b<=tmp){
a.g[i]=mid;
l=mid+1;
}
else{
r=mid;
}
}
tmp-=a.g[i]*b;
if(tmp>bint(0))g.insert(g.end(),tmp.g.begin(),tmp.g.end());
}
g=a.g;
while(g.size()>1&&!g.back())g.pop_back();
/*
bint a;
a.g.resize(g.size()-b.g.size()+1);
for(int i=g.size()-b.g.size();i>=0;--i){
bint tmp(vector<int>(g.begin()+i,g.end()));
g.erase(g.begin()+i,g.end());
while(tmp>=b){
tmp-=b,++a.g[i];
}
if(tmp>bint(0))g.insert(g.end(),tmp.g.begin(),tmp.g.end());
}
g=a.g;
while(g.size()>1&&!g.back())g.pop_back();
*/
}
return *this;
}
bint &operator %= (const bint &b){
(*this)=(*this)-(*this)/b*b;
return *this;
}
bint Pow(int b){
bint ans(1);
int k=0;
while(b>=(1<<k))++k;
for(int i=k-1;i>=0;--i){
ans=ans*ans;
if(b>>i&1)ans=ans*(*this);
}
return ans;
}
friend bint operator + (const bint &a,const bint &b){
return bint(a)+=b;
}
friend bint operator - (const bint &a,const bint &b){
return bint(a)-=b;
}
friend bint operator * (const bint &a,const bint &b){
return bint(a)*=b;
}
friend bint operator / (const bint &a,const bint &b){
return bint(a)/=b;
}
friend bint operator % (const bint &a,const bint &b){
return bint(a)%=b;
}
friend bool operator == (const bint &a,const bint &b){
return a.g==b.g;
}
friend bool operator != (const bint &a,const bint &b){
return !(a.g==b.g);
}
friend bool operator < (const bint &a,const bint &b){
if(a.g.size()<b.g.size())return true;
if(a.g.size()>b.g.size())return false;
for(int i=a.g.size()-1;i>=0;--i){
if(a.g[i]<b.g[i])return true;
if(a.g[i]>b.g[i])return false;
}
return false;
}
friend bool operator > (const bint &a,const bint &b){
return b<a;
}
friend bool operator <= (const bint &a,const bint &b){
return !(a>b);
}
friend bool operator >= (const bint &a,const bint &b){
return !(a<b);
}
friend ostream &operator << (ostream &out,const bint &a){
string s="";
if(!a.g.back())s="0";
else{
int x=a.g.back();
while(x)s+=x%10+'0',x/=10;
reverse(s.begin(),s.end());
}
out<<s;
for(int i=(int)a.g.size()-2;i>=0;--i){
s="";
int x=a.g[i];
for(int j=0;j<D;++j){
s+=x%10+'0',x/=10;
}
reverse(s.begin(),s.end());
out<<s;
}
return out;
}
};
using bint=unsigned_bigint<10,1,mix_tag>;
#define N 1000010
string a,b;
int n,m;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>a>>b;
n=a.length(),m=b.length();
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
int las=-1;
for(int i=0,op=0;i<max(n,m);++i){
int x=(i>=n?0:a[i]-'0')+(i>=m?0:b[i]-'0')+op;
if(x>=10){
op=1;
las=i;
}
else{
op=0;
}
}
if(las<0){
cout<<0<<'\n';
return 0;
}
string _a=a,_b=b;
for(int i=0;i<=las;++i){
if(_a.length()<=i)_a.push_back('0');
_a[i]='0';
}
if(_a.length()<=las+1)_a.push_back('0');
++_a[las+1];
for(int i=0;i<=las;++i){
if(_b.length()<=i)_b.push_back('0');
_b[i]='0';
}
if(_b.length()<=las+1)_b.push_back('0');
++_b[las+1];
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
reverse(_a.begin(),_a.end());
reverse(_b.begin(),_b.end());
cout<<min(bint(_a)-bint(a),bint(_b)-bint(b))<<'\n';
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 3500kb
input:
10 99
output:
1
result:
ok answer is '1'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3548kb
input:
90 10
output:
10
result:
ok answer is '10'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
23425 487915
output:
12085
result:
ok answer is '12085'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
1 1
output:
0
result:
ok answer is '0'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
99 99
output:
1
result:
ok answer is '1'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
14 86
output:
14
result:
ok answer is '14'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3560kb
input:
899999999999999999999 100000000000000000001
output:
100000000000000000001
result:
ok answer is '100000000000000000001'
Test #8:
score: 0
Accepted
time: 50ms
memory: 40108kb
input:
615357649595284099508435993883986571313695656691562389866620971630644953030429613681442060702023197532680463771166724257258948140032009435767225187778914625685600736964207275868974321513156027752788270804733647164380664571327109020774746630643814103150883559720458844636326901760106285413007100737536...
output:
226164757855375706179130034126837577710545348626568907238536520434546544085882446273981029021778063112888523241983297218947698252532826120194967039881313867888258883810876610793168815193851023510269144054457285631520878535365581681349042349672439715344120755176307571379581412256786498122023796566813...
result:
ok answer is '226164757855375706179130034126...1032113015742081980588406310856'
Test #9:
score: 0
Accepted
time: 0ms
memory: 5536kb
input:
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
0
result:
ok answer is '0'
Test #10:
score: 0
Accepted
time: 73ms
memory: 38840kb
input:
946678535444896475642225008527348253117127344137446723931302495407581979054231432196768653557235697280697999349345542859864503525832718970888297969471590384454809084105146882526427617822167077225221683317423530502375438306992125794196668936915418103664819269986191955766257534524689071638219238188976...
output:
533214645551035243577749914726517468828726558625532760686975045924180209457685678032313464427643027193020006506544571401354964741672810291117020305284096155451909158948531174735723821778329227747783166825764694976245616930078742058033310630845818963351807300138080442337424654753109283617807618110239...
result:
ok answer is '533214645551035243577749914726...8583282299712982139175537021362'
Test #11:
score: 0
Accepted
time: 41ms
memory: 39168kb
input:
794946477760061325408107597512810946289384941381736255316518687888511341258007534679058032849319730631613743099733353038802970355718221088259886925518970281655634779851495550264110452025361079238655051609110357880450805087197804035613307707314768911650131971835865731706270390379379832722335057330470...
output:
205053522239938674591892402487189053710615058618263744683481312111488658741992465320941967150680269368386256900266646961197029644281778911740113074481029718344365220148504449735889547974638920761344948390889642119549194912802195964386692292685231088349868028164134268293729609620620167277664942669529...
result:
ok answer is '205053522239938674591892402487...4895693158694032335924691582580'
Test #12:
score: 0
Accepted
time: 42ms
memory: 39516kb
input:
740396512715746854480688476727726843695909844190398984187893683516689175082139997856915168192558523514785642438089549764358594098561796813209038321522889191781035343854374929109665898552729746770608711636305055090924461862639090335815510632703670463147194228154033606862279586041022594067305712355803...
output:
259603487284253145519311523272273156304090155809601015812106316483310824917860002143084831807441476485214357561910450235641405901438203186790961678477110808218964656145625070890334101447270253229391288363694944909075538137360909664184489367296329536852805771845966393137720413958977405932694287644196...
result:
ok answer is '259603487284253145519311523272...7124298880143408010404228204895'
Test #13:
score: 0
Accepted
time: 34ms
memory: 39036kb
input:
808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080...
output:
191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919191919...
result:
ok answer is '191919191919191919191919191919...9191919191919191919191919191920'
Test #14:
score: 0
Accepted
time: 11ms
memory: 35596kb
input:
999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999...
output:
1
result:
ok answer is '1'
Test #15:
score: 0
Accepted
time: 53ms
memory: 38204kb
input:
888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok answer is '111111111111111111111111111111...1111111111111111111111111111112'
Test #16:
score: 0
Accepted
time: 41ms
memory: 39760kb
input:
499999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999...
output:
499999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999...
result:
ok answer is '499999999999999999999999999999...9999999999999999999999999999999'
Test #17:
score: 0
Accepted
time: 56ms
memory: 38608kb
input:
902851346436306806616375942396607826120232155242259147614243592903405735290837981154314613604373937058180635157768204138128396693345023355887820571704408856138693881765209464570723015717187118417699724996521322468835282812828545349457610944807873712140962669646920063042802116551616341958682221180684...
output:
739784808063119079929960519131554991813736147608454624748722101820388330144313273774081346945197605998068619643008000320015228364440867297627844532995103260191004283851259488125663821507594499196247233749377082143689851535156330319615505969268510443807604553524147479720718432743772029026906290480988...
result:
ok answer is '739784808063119079929960519131...1948627624188898000206620879303'
Test #18:
score: 0
Accepted
time: 37ms
memory: 39640kb
input:
724416096404218447265833382721297139425723348230646412938535112399662200961459489276744159193709343615237043403451777684608176033864123303353042148426141106174503987074111702253415957879317805779143259309953292187561544285879213401013240932738394155151275424316854703682327362480740497418303833476481...
output:
275583903595781552734166617278702860574276651769353587061464887600337799038540510723255840806290656384762956596548222315391823966135876696646957851573858893825496012925888297746584042120682194220856740690046707812438455714120786598986759067261605844848724575683145296317672637519259502581696166523518...
result:
ok answer is '275583903595781552734166617278...8872930707584800540407644105638'
Test #19:
score: 0
Accepted
time: 38ms
memory: 39316kb
input:
179760883913929098769751954947190783986510762079451401291657475628833258870415316784826579026164324281062020081021320517742313824799906611937368746321612306269758496471784982997262378087781498524472377305471180347632989650011243499867679056925218306140508787728196557041840793032875464254908876021669...
output:
202391160860709012302480450528092160134892379205485987083425243711667411295846832151734209738356757189379799189786794822576861752000933880626312536783876937302415035282150170027376219122185014755276226945288196523670103499887565001323209430747816938594912122718034429581592069671245357450911239783305...
result:
ok answer is '202391160860709012302480450528...2823656215559711050462000001286'
Test #20:
score: 0
Accepted
time: 29ms
memory: 39048kb
input:
694093295978385763996081646122651163487393563403375307120640726515101625170981544132833099306255215328986417862623494481857751894930538664304406593098107350723363635953635761495109280467562145123198911580622745275722840557806514156432129827761280709147879094131413817732889425551527261432195522728058...
output:
255769660772460029135659150462029009323862269154134965970617506744888571963168440708845854207631866982569513435894446504364418923339414859467991484536976751318428793008155206466142281148699553779149059558262299962485591410811078329484901571300035768990820396518084796670337233215816256442433385117841...
result:
ok answer is '255769660772460029135659150462...5240882786975575043401117211469'
Test #21:
score: 0
Accepted
time: 42ms
memory: 39432kb
input:
300681870704322241560104970320057811567211737552516811385136323064072671173825819427397761947835599467617616151523159779966244586152970280628373138993914850714409848595061132786328706497489992388484505984334528900604134964071443214035814375461628216063519758155475552005548598916806141612427038578006...
output:
245470701274362774449400345544121088380094571024237326765419310035541831084665407865334639554935227551147676469232950570285818569364395955422076452513852795266969401671952897250009875595788582424670890141940295697590000618374944180311423441095906635772223869242769402714599365582728097188947527241436...
result:
ok answer is '245470701274362774449400345544...4786420933984638221599280514231'