#define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include//assert(); #include ///////// #define REP(i, x, n) for(int i = x; i < n; i++) #define rep(i,n) REP(i,0,n) #define P(p) cout<<(p)< ///////// #ifdef getchar_unlocked #define mygc(c) (c)=getchar_unlocked() #else #define mygc(c) (c)=getchar() #endif #ifdef putchar_unlocked #define mypc(c) putchar_unlocked(c) #else #define mypc(c) putchar(c) #endif ///////// typedef long long LL; typedef long double LD; typedef unsigned long long ULL; ///////// using namespace::std; ///////// #ifdef _DEBUG #define DEBUG_BOOL(b) assert(b) #else #define DEBUG_BOOL(b) #endif ///////// //#define MY_TIME_COUNT 1 #ifdef MY_TIME_COUNT #include #endif /////数値読み込み #define ENABLE_READER_ON(T) \ inline void reader(T &x){\ int k;x = 0;bool flag = true;\ while(true){\ mygc(k);\ if( k == '-'){\ flag = false;break;\ }\ if('0' <= k && k <= '9'){\ x = k - '0';break;\ }\ }\ if( flag ){\ while(true){\ mygc(k);\ if( k<'0' || '9'> 1) & 0x5555555555555555ULL; N = ((N >> 2) & 0x3333333333333333ULL) + (N & 0x3333333333333333ULL); N = ((N >> 4) + N) & 0x0F0F0F0F0F0F0F0FULL; return (int)( (N * 0x0101010101010101ULL) >> 56); } #define ketaMax 19 #define BASE_MAX (ULL)0xFFFFFFFFFFFFFFFF #define FIVE_POW_19 (unsigned long long)19073486328125 #define MASK16_00 (unsigned long long)0x000000000000FFFF #define MASK16_01 (unsigned long long)0x00000000FFFF0000 #define MASK16_02 (unsigned long long)0x0000FFFF00000000 struct bigNum{ public: int NumSize;//確保しているindex+1 int TopIndex;//値の入っているindex+1 vector Num;//10^6 bigNum(){ NumSize = 1; TopIndex = 1; Num.reserve(65536);//Num.reserve(51906); } int setFromString(const string& str); }; int Count(const vector& Num,const int NumSize){ int ret = 0; for(int i=0;i(NumSize,0); TopIndex = 1;//0の値が[0]に入っている int Q = 1 + (len-1)%ketaMax; unsigned long long firstNum = 0; int NumPos = 0; int strPos = 0; for(strPos = 0;strPosadd(calNum); this->Num[0] = firstNum;//最初の値。 unsigned long long CAL1,CAL2,CARR,CARR_UP; /////////////mul vector org; unsigned long long ter; unsigned long long calNum[4]; ///////////// CARR_UP = 0; while( strPos < len ){ for(int i=0;iNum; const int orgTopIndex = this->TopIndex; //値が入っている部分だけ0初期化 for(int i=0; iNum[i] = 0; } //unsigned long long CAL1=0; //unsigned long long CAL2=0; CARR=0; int i; for(i=0; i>16) * FIVE_POW_19; calNum[2] = ((ter & MASK16_02)>>32) * FIVE_POW_19; calNum[3] = (ter>>48) * FIVE_POW_19; CAL1 = this->Num[i];//値を持ってくる。 CAL2 = CAL1;//保存しておく CARR = CAL2 > (CAL1 += (CARR_UP));//下からの繰上げ//CARRのリセット CAL2 = CAL1; CARR += CAL2 > (CAL1 += (calNum[0]<<19) ); CAL2 = CAL1; CARR += CAL2 > (CAL1 += (calNum[1]<<35)); CAL2 = CAL1; CARR += CAL2 > (CAL1 += (calNum[2]<<51)); this->Num[i] = CAL1;//値を戻す。 CARR_UP =( ( ( calNum[0]>>(64-19) ) + ( calNum[1]>>(64-35) ) ) + ( ( calNum[2]>>(64-51) ) + (calNum[3]<<(3)) ) + CARR); } while( CARR_UP ){ CAL1 = this->Num[i];//値を持ってくる。 CAL2 = CAL1;//保存しておく CARR_UP = CAL2 > (CAL1 += (CARR_UP)); this->Num[i++] = CAL1;//値を戻す。 } if(i > this->TopIndex){ this->TopIndex = i; } DEBUG_BOOL(CARR_UP == 0); } return NumSize; } inline void solve(){ string str; reader(str); //char str[1000001]; //fread(str,1,1000001,stdin); ////////////////////////////// bigNum bn; bn.setFromString(str); //cout << "TopIndex\t" << bn.TopIndex << endl; //cout << "NumSize\t" << bn.NumSize << endl; writer( Count(bn.Num,bn.TopIndex) ); //mypc('\n'); } int main(void){ std::cin.tie(0); std::ios::sync_with_stdio(false); std::cout << std::fixed;//小数を10進数表示 //cout << setprecision(16);//小数をいっぱい表示する。16? #ifdef MY_TIME_COUNT LARGE_INTEGER freq; QueryPerformanceFrequency(&freq); LARGE_INTEGER start, end; QueryPerformanceCounter(&start); #endif solve(); #ifdef MY_TIME_COUNT QueryPerformanceCounter(&end); cout << (double)(end.QuadPart - start.QuadPart) / freq.QuadPart << "sec.\n"; #endif return 0; }