# Untitled

By: a guest on Apr 28th, 2012  |  syntax: None  |  size: 1.23 KB  |  hits: 11  |  expires: Never
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. }