• The number of divisors for some number $$$n$$$ with prime factorization $$$p_1^{a_1}p_2^{a_2} \dots p_k^{a_k}$$$ is $$$(a_1 + 1)(a_2 + 1) \dots (a_k + 1)$$$.
• You can try to find the value of the function $$$g$$$ for some number $$$n$$$ with a simple prime factorization $$$p^a$$$: $$$g(p^a) = \sum_{x=0}^{a} (x+1) = \frac{(a+1)(a+2)}{2}$$$.
• Then you can try to find the value of the function $$$g$$$ for some number $$$n$$$ with a bit more complex prime factorization $$$p^aq^b$$$: $$$g(p^aq^b) = \sum_{x=0}^{a}\sum_{y=0}^{b} (x+1)(y+1) = \big( \sum_{x=0}^{a} (x+1) \big) \big( \sum_{y=0}^{b} (y+1) \big) = \frac{(a+1)(a+2)}{2}\frac{(b+1)(b+2)}{2}$$$.
• And so on. You can easily see that the function $$$g$$$ is multiplicative.
• So the problem is reduced to the prime factorization of $$$n!$$$ which can be done by several ways (note that the limit for $$$n$$$ is small enough).

First we have to calculate f(i) for all 1<=i<=n;

We can do this in nlog(n) time;

ll divs[MAXN];
void find_f_of_i(int n) {
	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j += i) {
			divs[j]++;
		}
	}
}

Now g(n!) means f(1)+f(2)+f(3)+....f(n), because 1-n all are divisors of n!.

so just calculate the prefix sum of f(i).

ll pre[MAXN];
void pre_sum(int n) {
	for (int i = 1; i <= n; i++) {
		pre[i] = pre[i - 1] + divs[i];
	}
}

Now answer all the queries in O(1)

#include<bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename T>  using oset =
    tree<T, null_type, less<T>,
    rb_tree_tag, tree_order_statistics_node_update>;
#define odrkey order_of_key
#define fbodr find_by_order
#define ll long long
#define sq(a) ((a)*(a))
#define ull unsigned long long
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define watch(x) cout << (#x) << " is " << (x) << endl
#define pi 3.1415926536
#define nwl cout <<"\n";
#define MAXN 1000009
#define ff first
#define ss second
#define pb push_back
template<typename T_vector>
void output_vector(const T_vector &v, bool add_one = false, int start = -1, int end = -1) {
	if (start < 0) start = 0;
	if (end < 0) end = int(v.size());

	for (int i = start; i < end; i++)
		cout << v[i] + (add_one ? 1 : 0) << (i < end - 1 ? ' ' : '\n');
}
ll Pow(ll a, ll b) {
	if (a == 0) return 0LL;
	ll ans = 1;
	for (int i = 0; i < b; i++) {
		ans *= a;
	}
	return ans;
}
ll lcm(ll a, ll b) {
	return (a * b) / __gcd(a, b);
}
ll md = (ll) 1e9 + 7;
ll bigmod(ll a, ll b, ll m) {
	if (b == 0) return 1LL;
	ll tm = bigmod(a, b / 2, m);
	tm = (tm * tm) % m;
	if (b % 2) tm = (tm * a) % m;
	return tm;
}
ll ncr(ll n, ll r) {
	if (r > n - r) r = n - r;
	ll up = 1;
	ll down = 1;
	for (ll i = 0; i < r; i++) {
		up = (up * (n - i)) % md; /* md== mod */
		down = (down * (r - i)) % md;
	}
	return (up * bigmod(down, md - 2, md)) % md;
}
ll divs[MAXN];
ll pre[MAXN];
void find_f_of_i(int n) {
	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j += i) {
			divs[j]++;
		}
	}
}
void pre_sum(int n) {
	for (int i = 1; i <= n; i++) {
		pre[i] = pre[i - 1] + divs[i];
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	find_f_of_i(MAXN);
	pre_sum(MAXN);
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		cout << pre[n] << "\n";
	}
}

First find prime factorization of all number upto n to find the contribution of each prime in n!. This can be done $$$nlog(n)$$$ using sieve [maintaining spf].

Let our $$$val$$$ array contains the contribution of each prime.

we can calculate the answer upto i as

val[i]=(val[i-1]+val[i-1]*(((val[i]+1)*(val[i]+2))/2-1)+((val[i]+1)*(val[i]+2))/2-1);

As if prime p has contribution a, it will contribute to the answer as $$$div(p)+div(p2)+div(p^3)...+div(p^a)$$$ which is $$$2+3+...+(a+1)$$$ note that we are exculding 1 here to prevent double counting, we will add 1 at the end. Finally the final answer is $$$val[n]+1$$$

the problem is to find number of pairs $$$ (x , y) $$$ such that $$$ x | y | n! $$$

let $$$ n! = {p_1}^{a_1} . {p_2}^{a_2} \dots {p_k}^{a_k}$$$ , $$$ x = {p_1}^{b_1} . {p_2}^{b_2} \dots {p_k}^{b_k}$$$ and $$$ y = {p_1}^{c_1} . {p_2}^{c_2} \dots {p_k}^{c_k}$$$.

now because $$$ x | y | n! $$$ , for every $$$ i $$$ , $$$ {b_i} <= {c_i} <= {a_i} $$$ should be held.

so for each $$$ i $$$ you need to find number of pairs $$$ ({b_i} , {c_i}) $$$ such that $$$ 0 <= {b_i} <= {c_i} <= {a_i} $$$. and it's easy to see that there are $$$ \dfrac{({a_i + 1}).({a_i + 2})}{2} $$$ such pairs.

and the final answer is $$$ \dfrac{({a_1 + 1}).({a_1 + 2})}{2} . \dfrac{({a_2 + 1}).({a_2 + 2})}{2} . \dots \dfrac{({a_k + 1}).({a_k + 2})}{2} $$$ .

UPD : $$$ x | y $$$ denotes that y is divisible by x.

Auto comment: topic has been updated by Abdelaleem (previous revision, new revision, compare).