PROBLEM LINK:
Setter & Editorialist : Mayuresh Patle
Tester : Uttkarsh Bawankar
DIFFICULTY:
MEDIUM
PREREQUISITES:
Sieve of Eratosthenes, Segmented Sieve, Factors of a Number
PROBLEM:
Given 2 integers X and Y, you have to derive a password using following procedure:
- X and Y represent the range [X,Y].
- Let C_{min} be the minimum count of factors of any number in this range.
- S_{C_{min}} is the sum of all those numbers in the range [X,Y] which have C_{min} number of factors.
- Let C_{max} be the maximum count of factors of any number in this range.
- S_{C_{max}} is the sum of all those numbers in the range [X,Y] which have C_{max} number of factors.
- Let C_{sum} be the sum of counts of factors of those numbers in range [X,Y] for which the count of factors is neither C_{max} nor C_{min}.
- S' is the sum of all the numbers whose count of factors was added in C_{sum}, i.e. the sum of all the numbers in the range [X,Y] for which the count of factors is neither C_{max} nor C_{min}.
- The English Alphabets are indexed, starting from 'a' at index 0.
- F= \text{alphabet at index } (C_{min} \mod 26).
- M= \text{alphabet at index } (C_{sum} \mod 26)
- L= \text{alphabet at index } (C_{max} \mod 26).
- An alphabet must be in uppercase if its index is Even, and in lowercase if its index is Odd.
- The password contains exactly 5 fields in this format (without any spaces between them): \text{Alphabet Integer Alphabet Integer Alphabet}
- These 5 fields of the password are F,\ S_{C_{min}},\ M,\ S_{C_{max}} and L respectively.
- If S' is odd, then the actual password is the reverse of the derived password.
Notable Constraints:
- 1 \leq X \leq Y \leq 10^{12}
- 1 \leq Y - X + 1 \leq 5*10^5
QUICK EXPLANATION
Find and store all primes less than 10^6. For each testcase, calculate the required parameters by applying Segmented Sieve Algorithm on range [X,Y].
EXPLANATION:
The explanation is divided into some parts, try making your own approach first after reading each part. If you are stuck at some point, then you can refer the next part.
Observation 1
- We know that any number N can be represented in the form p_1^{c_1}*p_2^{c_2}* \dots * p_n^{c_n} where p_1,p_2,\dots,p_n are prime factors of N and c_i is the maximum power of p_i (for i \in [1,n]) which divides N.
- Now, any factor of N can have any of these prime factors p_i multiplied 0 to c_i times in its representation in the above format. This will be applicable for all i \in [1,n].
- Hence, total number of factors of the number N will be (c_1+1)*(c_2+1)*\dots*(c_n+1)
Observation 2
For the given range of numbers, there can be at most 1 prime factor of any number which will be greater than 10^6. And, if it exists then its maximum power which divides the number will be exactly 1.
Proof for Observation 2
Because the product of any two (or more) numbers greater than 10^6 will be greater than 10^{12}.
Observation 3
We can derive the above form for any number in the given range with the help of primes in range [1,10^6]. And, we can find and store these primes in O(log(log(10^6)) using Sieve of Eratosthenes.
Observation 4
Length of the range [X,Y] is small enough to store the prime factors for each number in this range. In other words, you are allowed to make Y-X+1 arrays, such that i^{th} array, say pf[i], contains all the primes factors of i+X which are less than 10^6. You can do this by applying segmented sieve on this range.
Segmented Sieve
Let’s say we have stored all the prime numbers less than 10^6 in a container named primes.
First of all, initialise Y-X+1 empty containers, say pf[0\dots (Y-X+1)].
For each p \in primes do:
- i=p* \lceil \frac{X}{p} \rceil //(this will initialise i as the first multiple of p which is greater than X.
- while i\leq Y do:
- Insert p in (i-X)^{th} Container, i.e. insert p in pf[i-X].
- i = i + p //(If i is a multiple of p, then i+p will be a multiple of p too).
Now, for each i \in [0,Y-X+1], the i^{th} container, pf[i] will contains the prime factors of i+X.
Observation 5
For each prime factor p \in pf[i], you can keep on dividing and updating the value of tmp, where tmp=i+X initially, and count how many times p divides tmp.
Hence, you can now calculate the total number of factors of i+X for each i \in [0,Y-X+1].
Observation 6
What else are you expecting now? Remaining task is all about implementation!
You can refer the C++ solution for the implementation.
Time Complexity : O( (N+T*L)*log(log(N))), here N=10^6 and L=Y-X+1.
SOLUTIONS:
C++ Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
typedef vector <ll> vll;
#define chk(c) cerr<<#c<<" : "<<c<<"\n"
const ll N=1e6+1, oo=LLONG_MAX;
vll primes; //This will store all prime numbers till 10^6
vector <vll> pf; //pf[i] will store all primes factors<10^6 for i+X
//sieve of eratosthenes, stores all prime numbers till 10^6 in primes
void generate_primes()
{
ll r=sqrt(N)+1,i,j;
vll p(N,1);
p[0]=p[1]=0;
for(i=2;i<r;++i) if(p[i]) for(j=i*i;j<N;j+=i) p[j]=0;
for(i=0;i<N;++i) if(p[i]) primes.pb(i);
}
//stores the primes factors<10^6 for each number in range [l,r]
void prime_fctrs(ll l,ll r)
{
ll i;
pf.assign(r-l+1,vll()); //reset pf
for(ll prime:primes)
{
for(i=((l+prime-1)/prime)*prime;i<=r;i+=prime)
{
pf[i-l].pb(prime); //add currennt prime to pf[i]
}
}
}
//returns password based on the parameter values
string get_password(ll Cmin, ll Cmax, ll Csum, ll SCmin, ll SCmax, ll S)
{
char a[]="Aa";
Cmin %= 26;
Csum %= 26;
Cmax %= 26;
char F = a[Cmin & 1] + Cmin;
char M = a[Csum & 1] + Csum;
char L = a[Cmax & 1] + Cmax;
string pwd = F + to_string(SCmin) + M + to_string(SCmax) + L;
if(S & 1) reverse(pwd.begin(),pwd.end());
return pwd;
}
//returns password for given range
string password(ll X,ll Y)
{
ll Cmin=oo, SCmin=0; //initially Cmin = infinity
ll Cmax=0, SCmax=0; //initially Cmax = 0
ll Csum=0, S=0;
//S will store sum of counts of factors of all numbers
ll min_freq = 0; //stores the count of occorrences of Cmin
ll max_freq = 0; //stores the count of occorrences of Cmax
ll i, curr, pp, fc, tmp;
for(i=0;i+X<=Y;++i)
{
tmp=curr=i+X;
fc=1; //Initially factor count = 1
for(ll p:pf[i])
{
pp=0; //power of prime which divides i+X
while(tmp%p==0) ++pp,tmp/=p; //increment power
fc*=pp+1; //update factor count
}
if(tmp>1) //prime factor > 10^6
{
fc*=2ll;
}
if(fc==Cmin) //update parameters related to Cmin
{
SCmin+=curr;
++min_freq;
}
if(fc==Cmax) //update parameters related to Cmax
{
SCmax+=curr;
++max_freq;
}
Csum+=fc; //Add current factor count to CSum
S+=curr; //Add current number to S
if(fc<Cmin) //update Cmin
{
Cmin=fc;
SCmin=curr;
min_freq=1;
}
if(fc>Cmax) //update Cmax
{
Cmax=fc;
SCmax=curr;
max_freq=1;
}
}
//update Csum and S'
if(Cmin==Cmax)
{
Csum=0;
S=0;
}
else
{
Csum -= min_freq*Cmin + max_freq*Cmax;
S -= SCmin + SCmax;
}
//Now S contains the value of S' as described in the problem
//Uncomment the following part to check the calculated values
/*
chk(Cmin); chk(Csum); chk(Cmax);
chk(SCmin); chk(SCmax); chk(S);
chk(min_freq); chk(max_freq);
*/
return get_password(Cmin,Cmax,Csum,SCmin,SCmax,S);
}
int main()
{
//fast io
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll T,X,Y;
generate_primes(); //store primes till 10^6
cin>>T;
while(T--)
{
cin>>X>>Y;
prime_fctrs(X,Y); //store prime factors for range [X,Y]
cout<<password(X,Y)<<"\n"; //Compute & print the password
}
return 0;
}
Python 3 Solution
n=10**6+1
p=[1]*n
r=int(n**.5)+1
primes=[]
for i in range(2,r):
if p[i]:
primes.append(i)
for j in range(i*i,n,i): p[j]=0
for i in range(r,n):
if p[i]: primes.append(i)
pf=[]
def init(l,r):
global pf
t=r-l+1
pf=[[] for _ in range(t)]
for p in primes:
for i in range(p*((l+p-1)//p),r+1,p):
pf[i-l].append(p)
def fc(n,l):
ans=1
for p in pf[n-l]:
c=0
while n%p==0: n,c=n//p,c+1
ans*=c+1
if n>1: ans<<=1
return ans
for _ in range(int(input())):
x,y=map(int,input().split())
init(x,y)
Cmin,Cmax,Csum,SCmax,SCmin,S=10**20,0,0,0,0,0
fmin,fmax=0,0
for i in range(x,y+1):
c=fc(i,x)
if c==Cmin:
SCmin,fmin=SCmin+i,fmin+1
if c==Cmax:
SCmax,fmax=SCmax+i,fmax+1
S,Csum=S+i,Csum+c
if c<Cmin:
Cmin,SCmin,fmin=c,i,1
if c>Cmax:
Cmax,SCmax,fmax=c,i,1
if Cmin==Cmax: Csum,S=0,0
else:
Csum-=fmin*Cmin+fmax*Cmax
S-=SCmin+SCmax
Cmin,Cmax,Csum=Cmin%26,Cmax%26,Csum%26
F,M,L=[chr(x+ord('a' if x&1 else 'A')) for x in [Cmin,Csum,Cmax]]
pwd=F+str(SCmin)+M+str(SCmax)+L
if S&1: pwd=pwd[::-1]
print(pwd)