IamLupo

Project Euler - Problem 73

Apr 29th, 2016
206
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <math.h>
  5. #include <string.h>
  6. #include <stdlib.h>
  7.  
  8. using namespace std;
  9.  
  10. /*
  11.     How many fractions lie between 1/3 and 1/2 in the sorted set of
  12.     reduced proper fractions for d = 12,000?
  13. */
  14.  
  15. /*
  16.     Data:
  17.         1, 0, 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 3, 2, 3, 3, 3, 3, 4, 3, 4, 4,
  18.         4, 4, 5, 4, 5, 5, 5, 5, 6, 5, 6, 6, 6, 6, 7, 6, 7, 7, 7, 7, 8, 7,
  19.         8, 8, 8, 8, 9, 8, 9, 9, 9, 9, 10, 9, 10, 10, 10, 10,
  20.    
  21.     Formula:
  22.         a(n) = floor(n/6)+1 unless n=1(mod6); if n=1(mod6), a(n) = floor(n/6)
  23.    
  24.         Bob Selcoe, Sep 27 2014
  25.    
  26.     Reference:
  27.         https://oeis.org/A103221
  28. */
  29. long long A103221(long long n) {
  30.     if(n % 6 == 1)
  31.         return n / 6;
  32.     else
  33.         return (n / 6) + 1;
  34. }
  35.  
  36. long long countProperFractions(int l) {
  37.     int i, j;
  38.     long long r;
  39.     vector<int> mu(l + 1, 0);
  40.    
  41.     //Init
  42.     r = 0;
  43.    
  44.     mu[1] = 1;
  45.    
  46.     for(i = 1; i <= l; i++) {
  47.         //Generate Mobius
  48.         for(j = 2 * i; j <= l; j += i)
  49.             mu[j] -= mu[i];
  50.        
  51.         //Calculate Mobius inverse values
  52.         if(i >= 2)
  53.             for(j = 2; i * j <= l; j++)
  54.                 r += mu[i] * A103221(j);
  55.        
  56.         if(i >= 4)
  57.             r += A103221(i);
  58.     }
  59.        
  60.     return r;
  61. }
  62.  
  63. int main() {
  64.     cout << "result = " << countProperFractions(12000) << endl;
  65.    
  66.     return 0;
  67. }
RAW Paste Data