Solution to "A huge Sum" on Hackerearth

huge_sum.cpp

#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL;
 
const int MAX = 10000001;
const int MOD = 1e9 + 7;
 
#define inchar          getchar_unlocked
#define outchar(x)      putchar_unlocked(x)
 
template<typename T> void inPos(T &x) {
	x = 0;
	register T c = inchar();
	while((c<48) || (c>57)) {
		c = inchar();
	}
	for(; c<48 || c>57; c = inchar()) ;
	for(; c>47 && c<58; c = inchar()) {
		x = (x<<3) + (x<<1) + (c&15);
	}
}
 
template<typename T> void outPos(T n) {
	char snum[65]; 
	int i = 0; 
	do {
		snum[i++] = n % 10 + '0';
		n /= 10;
	} while(n);
	i = i - 1;
	while (i >= 0) {
		outchar(snum[i--]);
	}
	outchar('\n');
}
 
int add(int a, int b) {
	int res = a + b;
	return (res >= MOD ? res - MOD : res);
}
 
int mul(int a, int b) {
	LL res = (LL)a * b;
	return (res >= MOD ? (int)(res % MOD) : (int)res);
}
 
int p_k[9];
int lp[MAX];
vector<int> primes;
int prefix[MAX][8];
int distinct_primes[MAX];
 
void factor_sieve() {
	lp[1] = 1;
	for (int i=2; i<MAX; ++i) {
		if (lp[i] == 0) {
			lp[i] = i;
			primes.push_back (i);
		}
		for (int j=0; j<primes.size() && primes[j]<=lp[i]; ++j) {
			int x = i * primes[j];
			if (x >= MAX) break;
			lp[x] = primes[j];
		}
	}
}
 
void pre_compute() {
	for(int i=2; i<MAX; ++i) {
		if (lp[i] == i) {
			distinct_primes[i] = 1;
		}
		else {
			int w = i / lp[i];
			distinct_primes[i] = distinct_primes[w];
			if (w % lp[i] != 0) {
				distinct_primes[i] += 1;
			}
		}
		for(int j=0; j<8; ++j) {
			prefix[i][j] = prefix[i-1][j];
		}
		prefix[i][distinct_primes[i]-1] += 1;
	}
}
 
int main() {
	#ifndef ONLINE_JUDGE
		freopen("inp.txt", "r", stdin);
	#endif
	factor_sieve();
	pre_compute();
	int t, n, k, temp, ans;
	int i, x, i_nxt;
	inPos(t);
	while(t--) {
		inPos(n), inPos(k);
		p_k[0] = 1;
		for(int j=1; j<9; ++j) {
			p_k[j] = mul(p_k[j-1], k);
		}
		ans = n;
		i = n, x = 1;
		i_nxt = n / (x + 1);
		while(i - i_nxt > 1 && i_nxt > 0) {
			temp = 0;
			for(int j=1; j<9; ++j) {
				temp = add(temp, mul(p_k[j], prefix[i][j-1] - prefix[i_nxt][j-1]));
			}
			ans = add(ans, mul(temp, x));
			x += 1;
			i = i_nxt;
			i_nxt = n / (x + 1);
		}
		for(int m=2; m<=i; ++m) {
			temp = mul(p_k[distinct_primes[m]], (n / m));
			ans = add(ans, temp);
		}
		outPos(ans);
	}
	// cerr << clock() / (double)CLOCKS_PER_SEC << "\n";
	return 0;
}