Solution of 12043 - Dvisor

Problem Description
source:https://uva.onlinejudge.org/external/120/12043.html


Let us define the functions d(n) and σ(n) as 
d(n) = number of divisors of n 
σ(n) = summation of divisors of n 

Here divisors of n include both 1 and n. For example divisors of 6 are 1, 2, 3 and 6. So d(6) = 4 and σ(n) = 12. 
Now let us define two more function g(a, b, k) and h(a, b, k) as 

g(a, b, k) = ∑ i d(i) 
h(a, b, k) = ∑ i σ(i) 

Where a ≤ i ≤ b and i is divisible by k. 


For example, g(5, 12, 3) = d(6)+d(9)+d(12) = 4+3+6 = 13 and h(5, 12, 3) = σ(6)+σ(9)+σ(12) = 13 + 13 + 28 = 53. Given a, b, k you have to calculate g(a, b, k) and h(a, b, k).

Input 

The first line of the input file contains an integer T (T ≤ 75) which denotes the total number of test cases. The description of each test case is given below: Three integers in a line. First integer is contains a, second integer is b and third integer is k. You may assume 0 < a ≤ b ≤ 105 , 0 < k < 2000. 

Output 

For each test case print one line containing g(a, b, k) and h(a, b, k) separated by a space as defined above. 

Sample Input 

2 
5 12 3 
1 100 3 

Sample Output 

13 53
217 3323 

Solution:

#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include<stdio.h>
#define max 100001

using namespace std;
void generate();
long int dividor[max], sumdividor[max];

void generate()
{
    long int i, j, k;
    for(i=1;i<=max;i++)
    {
        dividor[i]=1;
        sumdividor[i]=1;
    }

    for(i=2;i<=max;i++)
    {
        dividor[i]+=1;
        sumdividor[i]+=i;
        for(j=i+i;j<=max;j=j+i)
        {
           dividor[j]+=1;
           sumdividor[j]+=i;
        }
    }
}

int main()
{
    long int t, a, b, i, j, k, m, div;
    long long int sum;
    generate();
    while(scanf("%ld",&t)==1)
    {
        for(i=1;i<=t;i++)
        {
            div=0;
            sum=0;
            scanf("%ld%ld%ld", &a,&b,&k);
            for(j=a;j<=b;j++)
            {
                if(j%k==0)
                {
                    div+=dividor[j];
                    sum+=sumdividor[j];
                }
            }
            printf("%ld %lld\n", div, sum);
        }
    }
    return 0;
}