PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: adj_alt
Tester: apoorv_me
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Elementary number theory
PROBLEM:
Given a number X, answer Q queries of the following form:
- Given P, find the number of Y such that \gcd(X, Y)^P = \text{lcm}(X, Y)
EXPLANATION:
To solve this task, it’s helpful to look at what the condition on gcd and lcm means in terms of the prime factorizations of X and Y.
Let’s prime factorize X and Y, so that
Note that we use the same set of primes for both numbers for the sake of convenience (meaning some of the a_i and/or b_i are allowed to be 0).
Then, it’s well-known that
So, \gcd(X, Y)^P = \text{lcm}(X, Y) means that for each prime p_i, we want \max(a_i, b_i) = P\cdot \min(a_i, b_i).
In particular, this means that either b_i = P\cdot a_i, or b_i = \frac{a_i}{P}.
Now, all the a_i values are fixed, and can be found by just prime factorizing X (even the straightforward \mathcal{O}(\sqrt{X}) algorithm is fast enough here).
Further, Y is defined uniquely by the choices we make for each b_i (after all, a positive integer is determined uniquely by its prime factorization).
Observe that:
- b_i = P\cdot a_i is always an available choice.
- b_i = \frac{a_i}{P} is available if and only if a_i is a multiple of P.
So, suppose there are M values of a_i that are multiples of P.
The answer is 2^M, since only for those primes we have two options, and everything else is fixed.
There is one edge case: for P = 1, P\cdot a_i = \frac{a_i}{P}, so we only have one option for each prime (meaning the answer is 1).
Thus, for each query, all that needs to be done is to count the number of a_i that are multiples of P.
Prime factorize X once and store all the a_i; then observe that there can only be \mathcal{O}(\log X) values of a_i anyway (since X can’t have more than \log_2 X distinct prime factors), so counting the number of them that are multiples of P can be done by just iterating over them all.
Finally, since the answer is 2^M for some M \leq \log_2 X, the answer fits into a 32-bit integer easily, and the modulo is irrelevant!
TIME COMPLEXITY:
\mathcal{O}(\sqrt{X} + Q\log X) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// template<typename T>
// using oset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
void actualcode();
#define ll long long int
#define endl "\n"
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
int mod = 1e9 + 7;
ll max3(ll a, ll b, ll c) { return (max(max(a, b), c)); }
ll max4(ll a, ll b, ll c, ll d) { return (max(max(max(a, b), c), d)); }
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
void YES() { cout << "YES" << endl; }
void NO() { cout << "NO" << endl; }
void yes() { cout << "Yes" << endl; }
void no() { cout << "No" << endl; }
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// #ifndef ONLINE_JUDGE
// freopen("Test_Case_3.txt","r",stdin);
// freopen("output8meh.txt","w",stdout);
// #endif
actualcode();
}
int sieve[40005];
void Sieve()
{
for (int i = 0; i < 40005; i++)
{
sieve[i] = 1;
}
for (ll i = 2; i < 40005; i++)
{
if (sieve[i] == 1)
{
for (ll j = i * i; j < 40005; j = j + i)
{
sieve[j] = 0;
}
}
}
}
void actualcode()
{
int t = 1;
cin >> t;
ll zero=0;
Sieve();
vector<int> prs;
for(int i=2;i<40005;i++)
{
if(sieve[i]) prs.push_back(i);
}
while (t--)
{
long long x;
cin>>x;
int q;
cin>>q;
ll temp;
int p;
int cnt=0,cnt1=0;
ll ans;
vector<int> pws;
temp=x;
for(auto it:prs)
{
cnt=0;
while(temp%it==0)
{
temp/=it;
cnt++;
}
if(cnt!=0)
{
pws.push_back(cnt);
}
}
while(q--)
{
cin>>p;
if(p==1)
{
cout<<1<<endl;
}
else
{
ans=1;
for(auto it:pws)
{
if(it%p==0)
{
ans*=2;
}
}
cout<<ans<<endl;
}
}
}
}
Tester's code (C++)
#ifndef LOCAL
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt,fma")
#endif
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "../debug.h"
#else
#define dbg(...) "11-111"
#endif
struct input_checker {
string buffer;
int pos;
const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";
input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
buffer.push_back((char) c);
}
}
int nextDelimiter() {
int now = pos;
while (now < (int) buffer.size() && !isspace(buffer[now])) {
now++;
}
return now;
}
string readOne() {
assert(pos < (int) buffer.size());
int nxt = nextDelimiter();
string res;
while (pos < nxt) {
res += buffer[pos];
pos++;
}
return res;
}
string readString(int minl, int maxl, const string &pattern = "") {
assert(minl <= maxl);
string res = readOne();
assert(minl <= (int) res.size());
assert((int) res.size() <= maxl);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}
int readInt(int minv, int maxv) {
assert(minv <= maxv);
int res = stoi(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
long long res = stoll(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
auto readInts(int n, int minv, int maxv) {
assert(n >= 0);
vector<int> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readInt(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
auto readLongs(int n, long long minv, long long maxv) {
assert(n >= 0);
vector<long long> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readLong(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
};
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
input_checker input;
int T = input.readInt(1, 1000); input.readEoln();
while(T-- > 0) {
int N = input.readInt(1, (int)1e9); input.readSpace();
map<int, int> fac;
for(int l = 2 ; l * l <= N ; ++l) {
while(N % l == 0) {
++fac[l];
N /= l;
}
}
if(N > 1)
++fac[N];
int NQ = input.readInt(1, 200); input.readEoln();
for(int i = 0 ; i < NQ ; ++i) {
int P = input.readInt(1, (int)1e9); input.readEoln();
if(P == 1) {
cout << 1 << '\n';
continue;
}
int cnt = 0;
for(auto &[a, b]: fac)
cnt += b % P == 0;
cout << (1ll << cnt) << '\n';
}
}
input.readEof();
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
x, q = map(int, input().split())
pows = []
p = 2
while p*p <= x:
ct = 0
while x%p == 0:
x //= p
ct += 1
if ct > 0: pows.append(ct)
p += 1
if x > 1: pows.append(1)
for i in range(q):
p = int(input())
ans = 1
for ai in pows:
if p > 1 and ai%p == 0: ans *= 2
print(ans)
