UVa : 12043 (Divisors)



// http://uva.onlinejudge.org/external/120/12043.html
// Runtime: 0.132
// Tag: Divisor, preCalculation

#include <stdio.h>
#include <math.h>
#define N 100000

int d [N + 5];
double sigma [N + 5];

int main ()
{
    // precalculation

    d [1] = 1;
    sigma [1] = 1;

    for ( int i = 2; i <= 100000; i++ ) {
        int len = (int) sqrt (i);
        d [i] = 2;
        sigma [i] = 1 + i;
        for ( int j = 2; j <= len; j++ ) {
            if ( i % j == 0 ) {
                d [i] += 2;
                sigma [i] += j;
                sigma [i] += (i / j);
            }
        }

        if ( len * len == i ) { d [i]--; sigma [i] -= len; }
    }

    int testCase; scanf ("%d", &testCase);
    int a, b, k;

    while ( testCase-- ) {
        scanf ("%d %d %d", &a, &b, &k);
        int num = (int) ceil (a / (double)k) * k;
        //printf ("num = %d\n", num);
        int g = 0;
        double h = 0;

        while ( num <= b ) {
            //printf ("d = %d s = %d\n", d [num], sigma [num]);
            g += d [num];
            h += sigma [num];
            num += k;
        }

        printf ("%d %0.lf\n", g, h);
    }

    return 0;
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s