Pagini recente » Cod sursa (job #826835) | Cod sursa (job #592191) | Cod sursa (job #3003067) | Cod sursa (job #1797139) | Cod sursa (job #1611109)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("sarpe.in");
ofstream fout("sarpe.out");
const int base= 10;
void h_write( vector <int> &x ) {
for ( int i= (int)x.size()-1; i>=0; --i ) {
fout<<x[i];
}
fout<<"\n";
}
void hh_sub( vector <int> &x, vector <int> &y ) {
for ( int i= 0; i<(int)x.size(); ++i ) {
if ( i<(int)y.size() ) {
x[i]-= y[i];
}
if ( x[i]<0 ) {
x[i]+= base;
--x[i+1];
}
}
while ( x.back()==0 && (int)x.size()>=2 ) {
x.pop_back();
}
}
void hh_mult( vector <int> &x, vector <int> &y ) {
vector <int> z;
z.resize( (int)x.size()+(int)y.size() );
for ( int i= 0; i<(int)x.size(); ++i ) {
int t= 0;
for ( int j= 0; j<(int)y.size() || t!=0; ++j ) {
z[i+j]+= t;
if ( j<(int)y.size() ) {
z[i+j]= z[i+j]+x[i]*y[j];
}
t= z[i+j]/base;
z[i+j]%= base;
}
}
while ( z.back()==0 && (int)z.size()>=2 ) {
z.pop_back();
}
x= z;
}
int main( ) {
string s;
fin>>s;
vector <int> n;
for ( int i= (int)s.size()-1; i>=0; --i ) {
n.push_back(s[i]-'0');
}
if ( (int)n.size()==1 && n[0]==1 ) {
fout<<"1\n";
} else {
vector <int> sol, aux;
sol= n;
hh_mult(sol, n);
hh_sub(sol, n);
sol[0]+= 2;
for ( int i= 0; i<(int)sol.size(); ++i ) {
if ( sol[i]>base ) {
if ( i==(int)sol.size()-1 ) {
sol.push_back(0);
}
++sol[i+1];
sol[i]-= base;
}
}
aux.push_back(2);
hh_mult(sol, aux);
h_write(sol);
}
return 0;
}