Don't like ads? PRO users don't see any ads ;-)
Guest

Untitled

By: a guest on Apr 28th, 2012  |  syntax: None  |  size: 1.23 KB  |  hits: 11  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. finding the sum of mod operations in a range
  2. #include <stdlib.h>
  3. #include <stdio.h>
  4. #include <math.h>
  5.  
  6. unsigned long long usqrt(unsigned long long n);
  7. unsigned long long modSum(unsigned long long a, unsigned long long b);
  8.  
  9. int main(int argc, char *argv[]){
  10.     unsigned long long a, b;
  11.     b = (argc > 1) ? strtoull(argv[argc-1],NULL,0) : 10000;
  12.     a = (argc > 2) ? strtoull(argv[1],NULL,0) : b;
  13.     printf("Sum of moduli %llu %% i for 1 <= i <= %llu: %llun",b,a,modSum(a,b));
  14.     return EXIT_SUCCESS;
  15. }
  16.  
  17. unsigned long long usqrt(unsigned long long n){
  18.     unsigned long long r = (unsigned long long)sqrt(n);
  19.     while(r*r > n) --r;
  20.     while(r*(r+2) < n) ++r;
  21.     return r;
  22. }
  23.  
  24. unsigned long long modSum(unsigned long long a, unsigned long long b){
  25.     if (a < 2 || b == 0){
  26.         return 0;
  27.     }
  28.     unsigned long long sum = 0, i, l, u, r = usqrt(b);
  29.     if (b < a){
  30.         sum += (a-b)*b;
  31.     }
  32.     u = (a < r) ? a : r;
  33.     for(i = 2; i <= u; ++i){
  34.         sum += b%i;
  35.     }
  36.     if (r < a){
  37.         u = (a < b) ? a : (b-1);
  38.         i = b/u;
  39.         l = b/(i+1);
  40.         do{
  41.             sum += (u-l)*b;
  42.             sum -= i*(u-l)*(u+l+1)/2;
  43.             ++i;
  44.             u = l;
  45.             l = b/(i+1);
  46.         }while(u > r);
  47.     }
  48.     return sum;
  49. }