We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
#include<iostream>#include<vector>typedefstd::vector<unsignedint>Exponents;// return exponent of a prime factor of C(n,k)// looks a bit like the logarithm:// C(n,k) = n! / ((n-k)! * k!)unsignedintchoose(constExponents&sums,unsignedintn,unsignedintk){returnsums[n]-(sums[n-k]+sums[k]);}intmain(){unsignedintlayer=200000;// 10^12 = 2^12 * 5^12unsignedintprime1=2;unsignedintexponent1=12;unsignedintprime2=5;unsignedintexponent2=12;std::cin>>layer>>prime1>>exponent1>>prime2>>exponent2;// analyze for each number between 0 and layer how often they contain prime1 and prime2ExponentsmulPrime1={0};ExponentsmulPrime2={0};for(unsignedintx=1;x<=layer;x++){autocurrent=x;unsignedintcount=0;// extract first prime (=2) as often as possiblewhile(current%prime1==0){current/=prime1;count++;}mulPrime1.push_back(count);count=0;// extract second prime (=5) as often as possiblewhile(current%prime2==0){current/=prime2;count++;}mulPrime2.push_back(count);}// sum1[x] = sum of mulPrime1[0 ... x]Exponentssum1;unsignedintcount=0;for(autox:mulPrime1){count+=x;sum1.push_back(count);}// the same stuff for the other primeExponentssum2;count=0;for(autox:mulPrime2){count+=x;sum2.push_back(count);}unsignedlonglongresult=0;for(unsignedinti=0;i<=layer;i++){// how often is each prime used by C(layer, i) ?autofound1=choose(sum1,layer,i);autofound2=choose(sum2,layer,i);// already enough ?if(found1>=exponent1&&found2>=exponent2){// no need to enter the inner-most loop, each iteration would succeedresult+=i+1;continue;}// note: abort early because of mirrored valuesfor(unsignedintj=0;j<=(i+1)/2;j++){if(found1+choose(sum1,i,j)>=exponent1&&found2+choose(sum2,i,j)>=exponent2){// found a matchresult++;// left and right side are identicalif(j<i/2)result++;}}}// and we're done !std::cout<<result<<std::endl;return0;}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #154: Exploring Pascal's pyramid.
You are viewing a single comment's thread. Return to all comments →