 # PROBLEM LINK:

Cheems VS Doge

Authors: Parth Dhorajiya and Rituj Aryan
Tester: Rohit Doshi

MEDIUM-HARD

# PREREQUISITES:

Number Theory, Dynamic Programming

# PROBLEM:

You are given three integers L, R, and S. Find the total number of subsets wherein the summation of the total number of prime factors of distinct numbers (lying between L and R, both inclusive) is equal to S.

The prime factor of a number is that divisor which has a factor as 1 and that number itself only. Can you help Cheems to solve this question?

# EXPLANATION:

Idea behind the problem is :-

1. Make a list v_1 in which i^{th} element stores the number of prime factors of the (L+i)^{th} element.
2. This is classic subset sum problem in which we have to count the number of subsets having sum = S.

For 1) – A number N can be represented in prime factorization as
N = a^p * b^q * c^r * d^s * e^t ...
where (a,b,c,d,e, ... are prime factors in increasing order)

For every number lying in range [L,R]:

Suppose current number is N.
count = 0; // Number of prime factors

for i = 2 to sqrt(N) {

if (N%i == 0) {
count++;
N = N/i;
}

while(N%i == 0) {
N = N/i;
}

if (N > 1) {
count++;
}

Store the count in list v1
(This denotes the number of prime factor of given number N)
}



Then sort v_1 in non-decreasing order.

For 2)

• We make dp[(R-L+1)+1][S+1] in which dp[i][j] denotes the number of subsets (considering first i elements of v_1) having sum j.

• Initialize dp[i]=1 (1st column of dp[ ][ ]) for valid 0 \leq i \leq (R-L+1), since there is always an empty subset { } having sum 0.

• For every particular element we have 2 options, to include it in the contribution of the sum or not.

• If v_1[i-1] > j, i.e. if the i^{th} element is greater than j (current sum).
Then its impossible to include it so the total number of subset would be same as of considering (first i-1 elements) having sum j.

• If v_1[i-1] \leq j, i.e we have option to include it.
So we add dp[i-1][j] + dp[i-1][j-v_1[i-1]],
first term means we consider first (i-1) elements that sums upto j, and
second term means we consider i^{th} element of v_1 and the sum remaining is (j-v_1[i-1]). So we would consider first (i-1) elements that sums to (j-v_1[i-1]).

• dp[n][s] would give our required answer.

CORNER CASE: (L = 1)

Now since our first element in v_1 would be 0
So we can initialize dp=1 and dp[i] = 2, 1 \leq i \leq (R-L+1)
Since we have 2 subsets having sum 0: ({ }, 0).

OR

Initialize 1st column in dp [ ] [ ] =1 as did before and multiply the answer we would get by 2. (because for every subset we can get a new subset by adding 0 to it.)

# SOLUTIONS:

Setter's Solution - CPP
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define A first
#define B second
#define lb long double
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define fo(i,n) for(i=0;i<n;i++)
#define mpp map<ll,ll>m;
#define vec vector<ll>v;
#define mod (ll)(1e9+7)
ll a;

void solve()
{
ll l,r,s,i,j,c=0,n,count=0;
cin>>l>>r>>s;
vector<ll> v,v1;

for(i=l;i<=r;i++)
v.pb(i);

for (auto e:v) {
ll a=e;
c=0;
for(i=2;i*i<=a;i++)
{
if(a%i==0)
{
c++;
a=a/i;
}
while(a%i==0)
{
a=a/i;
}
}
if(a>1)
c++;
v1.pb(c);
}
sort(v1.begin(),v1.end());
n=v1.size();
ll dp[n+1][s+1];
for(i=0;i<=n;i++)
dp[i]=1;
for(j=1;j<=s;j++)
dp[j]=0;
for(i=1;i<=n;i++){
for(j=1;j<=s;j++){
if(v1[i-1]<=j){
dp[i][j]=(dp[i-1][j]%mod+dp[i-1][j-v1[i-1]]%mod)%mod;
dp[i][j]%=mod;
}
else{
dp[i][j]=dp[i-1][j]%mod;
dp[i][j]%=mod;
}
}
}
if(l>1)
cout<<dp[n][s]%mod<<endl;
else{
cout<<((dp[n][s]%mod*2)%mod)<<endl;
}
}
int main()
{
fast
solve();
}

Tester's Solution - Python
from math import sqrt

mod = 10**9 + 7
MAXN = 1000001
SPF = [i for i in range(MAXN)]

# Calculating SPF (Smallest Prime Factor) for every number till MAXN.
# Time Complexity : O(n log(logn))
def manipulated_seive():
for i in range(4, MAXN, 2):
SPF[i] = 2

i = 3
while(i*i < MAXN):
if SPF[i] == i:
for j in range(i*i, MAXN, i):
if SPF[j] == j:
SPF[j] = i

i += 1

# A O(log n) function returning primefactorization by dividing by smallest prime factor at every step
def getFactorization(x):
ret = []
while (x != 1):
ret.append(SPF[x])
x = x // SPF[x]

return len(set(ret))

def subsetSum(numbers, sum):
array =  +  * (sum)
for current_number in numbers:
for num in range(sum - current_number, -1, -1):
if array[num]:
array[num + current_number] = (array[num + current_number]%mod + array[num]%mod)%mod

return array[sum]%mod

manipulated_seive()
l, r, s = map(int, input().split())

primeDiv = []
for i in range(l, r+1):
primeDiv.append(getFactorization(i))

ans = subsetSum(primeDiv, s)%mod
print(ans)


Feel free to share your approach. In case of any doubt or anything is unclear please ask it in the comment section. Any suggestions are welcomed. 