PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: eiandy_eahnady
Tester: mexomerf
Editorialist: iceknight1093
DIFFICULTY:
easy
PREREQUISITES:
Prime factorization (using a sieve)
PROBLEM:
Given an array A of length N and an integer M, find for each i the number of divisors of A_i\cdot M!.
M, A_i \leq 10^7 for this version.
EXPLANATION:
Read the solution to the easy version first.
In this version, since M \leq 10^7, there can be many primes in the factorization of M! (there will be \mathcal{O}\left(\frac{M}{\log M}\right) in fact, due to the prime number theorem).
This means the previous solution of computing the prime factorization of A_I\cdot M!, then computing the number of divisors from the product of powers will be too slow - we’ll need to iterate over all the primes (and there can be over 6\cdot 10^5 of them) for each index, which is much too slow.
However, let’s look at this from the opposite perspective: the A_i values remain small, and the prime factorizations of M! and M!\cdot A_i differ only in the primes dividing A_i.
This means only at most 8 primes change their powers between M! and M!\cdot A_i.
This allows us to do the following:
- Compute the prime factorization of M!, and from this factorization the number of its divisors - say D.
This is done only once, at the start.
Let b_i denote the power of i in this factorization (where b_i = 0 if i isn’t prime, of course). - Then, to compute the number of divisors of A_i\cdot M!:
- Prime factorize A_i in O(\log A_i) using the sieve.
- For each prime p dividing A_i, say with a power of k, the term in the product should be
(b_p + k), while it’s currently just b_p.
To quickly simulate this, simply divide D by b_p and then multiply it by (b_p + k). - The final value of D is the answer for this A_i.
- We perform at most \log_2 A_i divisions this way, and so even doing each of them in O(\log{MOD}) time using Fermat’s little theorem is fast enough.
Also, since A_i \leq 10^7, factorizing each A_i in square-root time is likely too slow.
Instead, we can use the fact that A_i \leq 10^7 to quickly prime factorize using a sieve.
Specifically, run a sieve of Eratosthenes to compute, for each number from 1 to 10^7, one of its prime divisors.
Then, to factorize A_i, simply look up the precomputed prime divisor of A_i (say p), and then factorize \frac{A_i}{p} instead (which can be done in the same way: divide out one of its prime divisors and so on).
That is, if \text{prm}[x] denotes the precomputed prime factor of x, the prime factors of A_i are exactly
Note that x can have at most \log_2 x prime divisors, so each A_i can be factorized in \mathcal{O}(\log A_i) time.
TIME COMPLEXITY:
\mathcal{O}(M\log\log M + N\log(\max A)\log{MOD}) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, M = 1e7 + 5,mod = 1e9 + 7;
#define int long long
int prime[M], n, m;
int b[N], mp[M];
int divs = 1;
vector<int> primes;
int add (int x , int y)
{
x %= mod;
y %= mod;
return (x + y) % mod;
}
int mul (int x , int y)
{
x %= mod;
y %= mod;
return (x * y) % mod;
}
void sieve() {
for (int i = 2; i < M; i++)
prime[i] = i;
for (int i = 2; (i * i) < M; i++) {
for (int j = (i * i); j < M; j += i) {
if (prime[i] == i) {
prime[j] = i;
}
}
}
}
int fastPower(int base, int power)
{
if(!power)
return 1;
int half = fastPower(base,power / 2);
int ans = mul(half,half);
if(power & 1) ans = mul(ans,base);
return ans;
}
int f(int x)
{
int ans = divs;
map<int, int> mp2;
while (x != 1)
{
mp2[prime[x]]++;
x /= prime[x];
}
for (auto i: mp2)
{
ans = mul(i.second + 1 + mp[i.first],ans) ;
ans = mul(ans, fastPower(mp[i.first] + 1, mod - 2));
}
return ans;
}
signed main()
{
sieve();
cin >> n >> m;
for (int i = 2; i <= m; ++i)
{
if (prime[i] == i)
{
primes.push_back(i);
}
}
for (int i = 2; i <= m; i++)
{
int x = i;
while (x != 1)
{
mp[prime[x]]++;
x /= prime[x];
}
}
for (auto i: primes)
{
divs = mul(divs,mp[i] + 1);
}
for (int i = 0, x; i < n; i++)
{
cin >> x;
b[i] = f(x);
}
for (int i = 0; i < n; i++)
{
cout << b[i] << " ";
}
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define md 1000000001
#define int long long
#define I long long
#define N 10000001
int dp[N] = {};
vector<int> prm;
int cnt[N] = {};
I modex(I a,I b,I m){
a=a%m;
if(b==0){
return 1;
}
I temp=modex(a,b/2,m);
temp=(temp*temp)%m;
if(b%2){
temp=(temp*a)%m;
}
return temp;
}
I mod(I a,I b,I m){
a=a%m;
b=b%m;
I c=__gcd(a,b);
a=a/c;
b=b/c;
c=modex(b,m-2,m);
return (a*c)%m;
}
int32_t main() {
for(int i = 2; i < N; i++){
if(dp[i] == 0){
int x = i;
prm.push_back(i);
while(x < N){
if(dp[x] == 0){
dp[x] = i;
}
x += i;
}
}
}
int n, m;
cin>>n>>m;
int num = 1;
for(int i = 0; i < prm.size(); i++){
int x = prm[i];
while(1){
int temp = m / x;
if(temp == 0){
break;
}
cnt[prm[i]] += temp;
x *= prm[i];
}
num *= (1 + cnt[prm[i]]);
num %= md;
}
int a[n];
int ans[n];
for(int i = 0; i < n; i++){
cin>>a[i];
int x = a[i];
ans[i] = num;
while(x > 1){
int y = dp[x];
int temp = 0;
while(x % y == 0){
temp++;
x /= y;
}
//cout<<cnt[y]<<"\n";
ans[i] = mod(ans[i] * (1 + cnt[y] + temp), (1 + cnt[y]), md);
//cout<<ans[i]<<"\n";
}
cout<<ans[i]<<" ";
}
cout<<"\n";
}