PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: mamaleshrh
Tester: iceknight1093
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Elementary combinatorics
PROBLEM:
Given N and X, count the number of arrays A of length \leq N whose LCM equals X.
EXPLANATION:
When dealing with GCD and LCM, it’s often useful to look at prime factorizations, and in particular how GCD and LCM can be computed using them.
A refresher
Let
be two integers written in terms of their prime factorizations.
Then,
This further generalizes to the LCM of any number of integers: for each prime, take the maximum power present in any of them.
GCD behaves the same way, just with \min instead of \max.
So, let
denote the prime factorization of X.
How do I compute this?
Prime factorizing an integer can be done with a small modification to the standard \mathcal{O}(\sqrt{X}) factorization algorithm.
For each p from 2 to \sqrt{X},
- If p doesn’t divide X, continue to the next one.
- If p does divide X, p is a prime factor of X.
Now, repeatedly divide out p from X as long as it’s possible, to get the power of p in X.
This works because the smallest integer dividing X must be a prime; and whenever we find a prime we remove all its occurrences from X.
This way, we continually find only the prime divisors of X, in increasing order.
Note that if X remains \gt 1 at the end of this process, X will itself be prime (and will be the last prime factor we’re looking for).
We know that for an array to satisfy \text{lcm}(A) = X, A must satisfy the conditions:
- For each prime p_i, the maximum power of p_i appearing in A should be exactly a_i.
- For any prime p that’s not one of the p_i, it shouldn’t appear in A at all.
- This is really just an extension of the first point, since a prime p that isn’t one of the p_i can be thought of as being p^0 in the prime factorization.
The length of the array is allowed to be anything from 1 to N.
Let’s fix this length to be L.
Now, for a fixed prime p_i, how many ways are there to distribute its powers to L elements, such that the maximum power is exactly a_i?
Well,
- Each element should receive a power between 0 and a_i.
That’s a_i + 1 options per element; for a total of (a_i + 1)^L options. - Out of these options, the only ones where the maximum is not a_i, are the ones where the maximum is strictly less than a_i.
This can only happen when every index receives a power that’s less than a_i.
The number of ways of doing this is a_i^L, since there are now a_i choices of power for each element. - Putting these together, the number of ways to distribute powers such that the maximum is exactly a_i, equals
This computation was only for the prime p_i.
We can perform the same computation for each of them, and multiply the values together to get the answer for L.
Note that this works because we’re dealing with primes; and every positive integer has a unique prime factorization. So, fixing positive integers as array elements is equivalent to fixing which prime powers they receive.
That is, for the fixed length L, the number of valid arrays is exactly
Compute this for all L from 1 to N and add them up to get the answer.
Note that k here is the number of distinct prime factors of X, which is \mathcal{O}(\log X); so doing this in \mathcal{O}(k) or \mathcal{O}(k\log N) for each L is still fast enough.
TIME COMPLEXITY:
\mathcal{O}(\sqrt{X} + N\log X) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define oset tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>//oset name name.order_of_key(#ele<k) *name.find_by_order(index) less_equal greater greater_equal
#define vi vector<int>
#define pii pair<int, int>
#define mii map<int, int>
#define rep(i, a, b) for (int i = a; i < b; i++)
#define int long long
#define ld long double
#define pb push_back
#define all(v) v.begin(), v.end()
#define back(v) v.rbegin(), v.rend()
#define yes cout << "YES" \
<< "\n";
#define no cout << "NO" \
<< "\n";
#define deb(a) cerr << #a << "=" << (a) << "\n";
#define nl "\n"
#define FastIO \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0)
using namespace std;
#define mod 998244353
const int oo = 1e18;
long long binpow(long long a, long long b, long long m)
{
a %= m;
long long res = 1;
while (b > 0)
{
if (b & 1)
{
res = res * a % m;
}
a = a * a % m;
b >>= 1;
}
return res;
}
void solve()
{
int n, x;
cin >> n >> x;
mii cnts;
for (int i = 2; i <= sqrt(x); i++)
{
if (x % i == 0)
{
while (x % i == 0)
{
cnts[i]++;
x /= i;
}
}
}
if (x != 1)
{
cnts[x]++;
}
vi powers;
vector<pii> pre_powers;
for (auto [num, pows] : cnts)
{
powers.pb(pows);
pre_powers.pb({pows, pows + 1});
}
int out = 0;
for (int i = 1; i <= n; i++)
{
int add = 1;
int j = 0;
for (auto it : powers)
{
// add *= ((binpow(it + 1, i, mod)) - (binpow(it, i, mod)) + mod) % mod;
auto [aa, bb] = pre_powers[j];
add *= (bb - aa + mod) % mod;
aa *= it;
bb *= (it + 1);
aa %= mod;
bb %= mod;
pre_powers[j] = {aa, bb};
add %= mod;
j++;
}
out += add;
out %= mod;
}
cout << out << nl;
}
signed main()
{
FastIO;
// freopen("P7_0.in", "r", stdin);
// freopen("P7_0.out", "w", stdout);
int test = 1;
cin >> test;
while (test--)
{
solve();
}
return 0;
}
Editorialist's code (Python)
mod = 998244353
for _ in range(int(input())):
n, x = map(int, input().split())
prime_factors = []
p = 2
while p*p <= x:
pw = 0
while x%p == 0:
x //= p
pw += 1
if pw > 0: prime_factors.append((p, pw))
p += 1
if x > 1: prime_factors.append((x, 1))
ans = 0
for l in range(1, n+1):
ways = 1
for p, pw in prime_factors:
ways = ways * (pow(pw+1, l, mod) - pow(pw, l, mod)) % mod
ans += ways
print(ans % mod)
