Problem Link : NUMFACT Problem - CodeChef
This is my code for above problem. My code is passing the test case but when I ran it it could only able pass subtask 1, not others. So, please help me out to figure out my mistake.
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main() {
// your code goes here
ll t;
cin>>t;
while(t--){
ll n;
cin>>n;
ll arr[n];
ll maximum = INT_MIN;
for(ll i = 0; i<n; i++){
cin>>arr[i];
maximum = max(maximum, arr[i]);
}
ll dp[maximum + 1];
memset(dp, 0, sizeof(dp));
for(ll i = 0; i<n; i++){
while(arr[i] % 2 == 0){
arr[i] = arr[i]/2;
dp[2]++;
}
for(ll j = 3; j < sqrt(arr[i]); j++){
while(arr[i] % j == 0){
arr[i] = arr[i]/j;
dp[j]++;
}
}
if(arr[i] > 2) dp[arr[i]]++;
}
ll count = 1;
for(ll i = 0; i <= maximum; i++){
count = count * (dp[i] + 1);
}
cout<<count<<endl;
}
return 0;
}
Hey after seeing this topic created by you I attempted the question in python and got AC
You can see my solution
Ask me if you have any doubt.
Thanks
Can you please explain your approach that you have picked up in your code?
Approach:
-Make in terms of prime power
factorize into prime numbers and store their powers,
Like if there are three 10’s
then,
[2,3] and [5,3]
Since A[i]<=1000000
So can make index-value array,
where index would be prime factors,
and value will be count of that prime factors, which we will initialize by 0.
-Just product of those (count+1) will be your answer.
This we do to se possiblities weather the prime numbers power are 0 or 1 or 2 or … count of
that prime numbers.
You can also use unordered_map (Standard template library) for storing the number of powers,
Which will optimized your code.
If you dont know about unordered_map, Can watch video on my channel,
In this video unordered_map is explored from 03:40,
Can also watch and learn other STL videos from my playlist.
yeah sure, So I do the prime factorization of all the numbers present in the array and store the prime number as many time it appears in the factorization
Example- Prime Factorization of 28 is 2,2,7
do the prime factorization of all the numbers and store the count of all the prime number that how many time it appears I used dictionary in Python you can use a map or something like that in CPP, then the I used the formula described in this article
Hope you got my point
Thanks
Let Number be N -
Prime factorisation of N be like - pa * qb * rc . . … .
here p , q , r = prime numbers and a , b ,c are powers (>0) of prime number , then -
Total number of factors = (a+1) * ( b+1) * (c+1) - - - -
Take Example :
N1 = 12
=> 22 * 31
=> Total number of factors = (a+1) * ( b+1) = 3*2 = 6
N2 = 48
=> 24 * 31
=> Total number of factors = (a+1) * ( b+1) = 5*2 = 10
Product = N1 * N2 = 12 * 48 = 576
=> 26 * 32
which is same as - (22 * 31 ) * (24 * 31 ) = 26 * 32
Now a simple thing we have to prime factorize each A[i] and count frequency of each prime and after that just multiply the (frequencies+1).
Now one more thing u do prime factorization each time A[i] log(A[i]) time which leads to time complexity N * ( A[i] log(A[i]) ) [ it will pass as constraints are small ] ,
But if the array size is 105 then it will give u TLE, as u r iterating almost 17 * 1010 times loop, so to avoid u can use Smallest prime factorization approach (google it ) , and prime factorize each A[i] in log(A[i]) time , so overall complexity will be Nlog(Max_element of arrray )
My solution (without SPF ) - Here
My Solution (With SPF ) - Here
This is exactly what I did in my code except that SPF thing. But still I am getting the wrong answer.
OMG!!! SORRRYYYY GUYS!! I just forgot to put ‘=’ operator in a for loop. But thanks a lot! And yh, I’ll google that SPF thing.
1 Like
