Here is the problem:- https://www.interviewstreet.com/challenges/dashboard/#problem/4e14a0058572a I just have to find out total number of divisors of n!^2. For this I did prime factorization of n! and total no. of divisors = (1+2*k1)(1+2*k2).... ,where kj is exponent of j'th prime factor. My code is:-
#include<iostream>
using namespace std;
int m =0;
void pass(long long*b,long long k,long long*a,long long i)
{
if(i==1)
return;
for(long long s=0;s<k;s++)
{
if(i%b[s]==0)
{
a[b[s]]++;
m=1;
pass(b,k,a,i/2);
break;
}
}
}
int main()
{
long long n;
cin>>n;
long long a[n+1];
for(long long j=0;j<=n;j++)
a[j]=0;
long long b[50000];
long long k =0;
for(long long i=2;i<=n;i++)
{
if(i==2)
{
a[i]++;
b[k]=i;
k++;
continue;
}
m =0;
pass(b,k,a,i);
// cout<<m<<endl;
if(m==0)
{
a[i]++;
b[k] = i;
k++;
}
}
long long s=1;
for(long long i = 0;i<=n;i++)
{
if(a[i]==0)
{
continue;
}
s*=(1+2*a[i]);
//cout<<i<<" "<<a[i]<<endl;
}
cout<<s%1000007<<endl;
}
can anyone tell how to calculate s%(10^6+7) regarding this problem for very large s(10^100 range)??
s *= (1 + 2 * a[i]) change to s = (s *(1+2*a[i]))%1000007;
NOTE:I dont know why "*" is not displayed s = (s there(1+2*a[i]))%1000007;
hey thanks...it works!!but for n=10^6 it's showing segmentation fault(core dumped error)??
I think that is because of memory limit on your computer try "Custom test" on Codeforces.
NOTE: I didnt mean your computer's memory, but settings of compiler which dont allow to make applications with memory more than some.
yeah..it shows TLE on custom test..:(
I think you need to precalc all primes firstly(Sieve of Eratosthenes or Linear sieve), and then find factorization of every i, this solution has
complexity.
ADD: Try to find for every number any of prime divisors, and then you can easily find factorization.
but thats what I am doing...calculating for n=2,n=3, n=4.dividing by previous prime before it which are stored in b[5000],i.e,2 & 3 if 4%2==0 a[2]++ and then argument 4/2 to function.So where should finding prime first will boost my algorithm...can u give an instance of your logic?
You try to divide by all primes, that less than current. It's not effective way. you can find factorization with time complexity O(number of prime divisors of k) = O(log k), finding any of prime divisors and making like it:
void find_factorization(int k) { while(k!=1) { div = some_prime_divisor[k]; ++a[div]; k/=div; } }
ok..i got it..i just have to find a single prime divisor of the number and from than run the type of function u have built..for that .. i find out all prime before n and check from beginning that if the prime divide or not..if it does, i should enter into your function and break that previous checking loop...am i right?
Little bit wrong. You can find all primes and some_prime_divisor using Sieve of Eratosthenes. Do you know what is Sieve of Eratosthenes?
It would be more faster than you've said.
yes i do..it's efficient only for small numbers..i am not getting why to use Eratosthenes if we do have better ways(storing previous primes and dividing and checking using them)...now give me a code snippet of your logic..its getting worse..
This is code, you just need to modify it to find some_prime_divisor for every i<=n
I'm sorry, there was mistake in previous code.
through this code your aim is to find first prime number which is divisor of n ..ok.suppose i found it.let it be k..than what?..the thing is you have confused me a bit..
Ok. My aim is to find some prime divisor for every i<=n and I want to do it fast enough. It could be done in
using Sieve of Eratosthenes. Then I want to find factorization of N! in a loop finding factorization for every i<=n If you cannot understand my suggestions,it's my solution.
..ok..now i think i have correctly implemented your logic.Here is code:- http://ideone.com/FqBb8
No, you don't. Try estimate time complexity of your solution... I suggested you to precalculate(it means that before main loop you already know some prime divisor for every number and you don't need to calculate it again) values of some prime divisors for every i<=n,but you try to find it on every iteration. Look at my code, firstly I found this values(they are in array p[]) and I also calculate value of k/p[k](they are in array d[]) to not do it in main program. And after that(**only after that**) I calculated values of array a[] where exponents of coorresponding primes.
I think my algo works far better than finding primes for each number distinctively..
I suggest to find only one (not every) prime divisor for every number of [1, N]