
Untitled
By: a guest on
Apr 28th, 2012 | syntax:
None | size: 1.23 KB | hits: 11 | expires: Never
finding the sum of mod operations in a range
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
unsigned long long usqrt(unsigned long long n);
unsigned long long modSum(unsigned long long a, unsigned long long b);
int main(int argc, char *argv[]){
unsigned long long a, b;
b = (argc > 1) ? strtoull(argv[argc-1],NULL,0) : 10000;
a = (argc > 2) ? strtoull(argv[1],NULL,0) : b;
printf("Sum of moduli %llu %% i for 1 <= i <= %llu: %llun",b,a,modSum(a,b));
return EXIT_SUCCESS;
}
unsigned long long usqrt(unsigned long long n){
unsigned long long r = (unsigned long long)sqrt(n);
while(r*r > n) --r;
while(r*(r+2) < n) ++r;
return r;
}
unsigned long long modSum(unsigned long long a, unsigned long long b){
if (a < 2 || b == 0){
return 0;
}
unsigned long long sum = 0, i, l, u, r = usqrt(b);
if (b < a){
sum += (a-b)*b;
}
u = (a < r) ? a : r;
for(i = 2; i <= u; ++i){
sum += b%i;
}
if (r < a){
u = (a < b) ? a : (b-1);
i = b/u;
l = b/(i+1);
do{
sum += (u-l)*b;
sum -= i*(u-l)*(u+l+1)/2;
++i;
u = l;
l = b/(i+1);
}while(u > r);
}
return sum;
}