### Abdelaleem's blog

By Abdelaleem, history, 7 weeks ago,

the problem ...

https://codeforces.com/group/H10hR2t6Sj/contest/338701/problem/J

Let M be a positive integer.

Let f(M) be the number of positive divisors of an integer M.

For example f(12)=6 and they are 1,2,3,4,6,12.

Let g(M) be The summation of number of divisors of the divisors of an integer M.

Mathematically we can say g(M)=∑i|Mf(i), where | means divides.

For example, g(12)=f(1)+f(2)+f(3)+f(4)+f(6)+f(12)=1+2+2+3+4+6=18.

You are given an integer n, Calculate g(n!).

* While ..( 1 ≤ n ≤ 1e6 ).*****

How i can solve this Problem ?

• +8

 » 7 weeks ago, # | ← Rev. 4 →   -12 .
 » 7 weeks ago, # |   +15 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).
 » 7 weeks ago, # | ← Rev. 2 →   +6 First we have to calculate f(i) for all 1<=i<=n;We can do this in nlog(n) time; f(i)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). Presumll 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) Full code#include #pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #include #include using namespace std; using namespace __gnu_pbds; template using oset = tree, 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 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"; } } 
•  » » 7 weeks ago, # ^ |   +7 What about all the divisors of n! that are more than n?
•  » » » 7 weeks ago, # ^ |   +39 Ah! My bad. That's why I always get a WA on pretest 2. ༎ຶ‿༎ຶ
 » 7 weeks ago, # |   0 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$
 » 7 weeks ago, # | ← Rev. 3 →   +6 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.
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   -11 What does “stick” denote in x|y|n! ? Does it means n % y == 0 && y % x == 0?
•  » » » 7 weeks ago, # ^ |   +14 time needed to write a comment > time needed to search in Google.
•  » » » » 7 weeks ago, # ^ | ← Rev. 4 →   0 Why google if it really is a divisibility?
•  » » 7 weeks ago, # ^ | ← Rev. 3 →   +1 Ah, got it: y here is every divisor of n! that goes into f(…) in this formula g(z) = f(div1) + … + f(div.m) and number of x’s is value of f(y) by f() defenition. Nice!
•  » » » 7 weeks ago, # ^ |   0 Can you plz write its code and share it. I am unable to understand the approach
 » 7 weeks ago, # |   0 Auto comment: topic has been updated by Abdelaleem (previous revision, new revision, compare).