fork(1) download
copy 
  1.  #include <stdio.h>
  2.  #include <time.h>
  3.  
  4. // sum of largest odd factor of numbers 1 to n
  5.  
  6.  unsigned long long biggestOddFactor(unsigned long long int n)
  7.  {
  8.     // return the biggest odd factor of a number
  9.      while(n%2 == 0)
  10.          n /= 2;
  11.      return n;
  12.  }
  13.  
  14.  unsigned long long naive(unsigned long long int n)
  15.  {
  16.     // sum the biggest odd factors of numbers from 1 to n
  17.     // without any optimizations
  18.      unsigned long long int ret = 0;
  19.      for (unsigned long long int j = 1; j <= n; ++j)
  20.          ret += biggestOddFactor(j);
  21.      return ret;
  22.  }
  23.  
  24.  unsigned long long oddsOnly (unsigned long long min, unsigned long long max);
  25.  unsigned long long evensOnly (unsigned long long min, unsigned long long max);
  26.  
  27.  unsigned long long smart (unsigned long long min, unsigned long long max)
  28.  {
  29.     // sum the biggest odd factors of numbers from min to max (inclusive)
  30.     // by summing the odds and evens separately
  31.      if (min == max)
  32.          return biggestOddFactor(min);
  33.  
  34.      return oddsOnly(min, max) + evensOnly(min, max);
  35.  }
  36.  
  37.  unsigned long long oddsOnly (unsigned long long min, unsigned long long max)
  38.  {
  39.     // sum the odd numbers from min to max (inclusive)
  40.     // using the rule that the sum of the first n odd numbers is n^2
  41.      unsigned long long ret = 0;
  42.      if ((min % 2) != 0)
  43.          ++min;
  44.      if ((max % 2) != 0)
  45.          --max;
  46.      if (min > max)
  47.          return 0;
  48.      if (min == max)
  49.          return min;
  50.      ++max;
  51.      return (max*max - min*min)/4;
  52.  }
  53.  
  54.  unsigned long long evensOnly (unsigned long long min, unsigned long long max)
  55.  {
  56.     // sum the largest odd factors of numbers from min to max (inclusive)
  57.     // using the rule that the sum of largest odd factors of even numbers is
  58.     // the same as for half those numbers
  59.      unsigned long long ret = 0;
  60.      if ((min % 2) == 0)
  61.          ++min;
  62.      if ((max % 2) == 0)
  63.          --max;
  64.      if (max < min)
  65.          return 0;
  66.      if (max == min)
  67.          return biggestOddFactor (max);
  68.      return oddsOnly (min/2, max/2) + evensOnly (min/2, max/2);
  69.  }
  70.  
  71.  int main()
  72.  {
  73.       unsigned long long int q = 880;
  74.       clock_t before, after;
  75.  
  76.       for (int i = 0; i < 10; ++i)
  77.       {
  78.  
  79.           before = clock();
  80.           unsigned long long int j = naive (q);
  81.           after = clock();
  82.           printf("q=%lld naive=%lld time=%d\n", q, j, (int) (after-before));
  83.  
  84.           before = clock();
  85.           unsigned long long int k = smart (1, q);
  86.           after = clock();
  87.           printf("q=%lld fast=%lld time=%d\n", q, j, (int) (after-before));
  88.  
  89.           q *= 3;
  90.       }
  91.  }
Success #stdin #stdout 0.02s 15232KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
q=880 naive=258168 time=2
q=880 fast=258168 time=1
q=2640 naive=2323272 time=3
q=2640 fast=2323272 time=0
q=7920 naive=20909120 time=9
q=7920 fast=20909120 time=0
q=23760 naive=188179896 time=27
q=23760 fast=188179896 time=0
q=71280 naive=1693615476 time=79
q=71280 fast=1693615476 time=1
q=213840 naive=15242521194 time=238
q=213840 fast=15242521194 time=1
q=641520 naive=137182662824 time=717
q=641520 fast=137182662824 time=0
q=1924560 naive=1234643789988 time=2152
q=1924560 fast=1234643789988 time=0
q=5773680 naive=11111793800234 time=6471
q=5773680 fast=11111793800234 time=0
q=17321040 naive=100006142687092 time=19284
q=17321040 fast=100006142687092 time=0
https://ideone.com/TtJpaq
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!