project-euler

https://projecteuler.net/
Log | Files | Refs | README

Euler_33.cpp (1839B)

      1 #include "Euler.h"
      2 
      3 std::vector<int> lowestTerm(int n, int d, std::vector<int> &p)
      4 {
      5     for (unsigned i = 0; i < p.size(); )
      6     {
      7         if ((n % p[i] == 0) && (d % p[i] == 0))
      8         {
      9             n /= p[i];
     10             d /= p[i];
     11 
     12             i = 0;
     13         }
     14         else
     15             ++i;
     16     }
     17 
     18     std::vector<int> l;
     19 
     20     l.push_back(n);
     21     l.push_back(d);
     22 
     23     return l;
     24 }
     25 
     26 void addDigitCancellingFraction(std::vector<int> &denom, std::vector<int> &numer, std::vector<int> &primes, std::vector<std::vector<int>> &dc_fractions, int n, int d, bool first)
     27 {
     28     if (denom[first] == numer[!first])
     29     {
     30         std::vector<int> lowest = lowestTerm(n, d, primes);
     31         std::vector<int> lowestCancelled = lowestTerm(numer[first], denom[!first], primes);
     32         if ((lowestCancelled[0] == lowest[0]) && (lowestCancelled[1] == lowest[1]))
     33             dc_fractions.push_back(lowest);
     34     }
     35 }
     36 
     37 int Euler::DigitCancellingFractionsDenominator()
     38 {
     39     std::vector<int> primes = EulerUtility::getPrimesUnderCeiling(52);
     40 
     41     std::vector<std::vector<int>> dc_fractions;
     42 
     43     for (int denominator = 10; denominator < 100; ++ denominator)
     44     {
     45         std::vector<int> denom = EulerUtility::intToDigits(denominator);
     46 
     47         for (int numerator = 10; numerator < denominator; ++numerator)
     48         {
     49             std::vector<int> numer = EulerUtility::intToDigits(numerator);
     50 
     51             addDigitCancellingFraction(denom, numer, primes, dc_fractions, numerator, denominator, true);
     52             addDigitCancellingFraction(denom, numer, primes, dc_fractions, numerator, denominator, false);
     53         }
     54     }
     55 
     56     int n = 1, d = 1;
     57 
     58     for (std::vector<int> fraction : dc_fractions)
     59     {
     60         n *= fraction[0];
     61         d *= fraction[1];
     62     }
     63 
     64     std::vector<int> lowestProduct = lowestTerm(n, d, primes);
     65 
     66     return lowestProduct[1];
     67 }