Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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;
- }
Advertisement
Add Comment
Please, Sign In to add comment