Page 2 of 3
Posted: Tue Feb 14, 2006 5:18 am
by wook
A simple one :
input
Code: Select all
25
2 3
2 4
2 5
2 7
4 73
5 29
6 329
1230 3728
23529 55444
50000 60000
90888 90888
2 100000
100001 200000
1000000 2000000
1999999 2000000
2000000 2000000
2 2000000
182 298149
16871 199290
34 28711
6163 6163
7777 7777
12345 12345
1725777 1725777
10 10
output
Code: Select all
3
5
8
13
325
94
2063
24762
424814
137488
13
1325890
1495090
17760797
38
19
33829803
4349639
2623043
336858
11
12
13
18
3
Recursion+DP to solve this Problem
Posted: Thu Feb 16, 2006 9:08 am
by mrahman
I use Recursion to generate all the PHI value. Then DP to store the summation. My Timing is: 0:00.865(2nd in Ranklist). What is the approach of Krzysztof Dul
Posted: Thu Feb 16, 2006 10:08 am
by Krzysztof Duleba
No recursion, just a well coded sieve (but there's still plenty of room for improvements
).
Posted: Thu Feb 23, 2006 1:20 pm
by chunyi81
Do you know how to factor the numbers from 1 to N in O(NlogN) time? It's a simple modification to the standard Sieve of Erastosthenes. That's a start.
The next step is to look at the formula for phi(n) that uses the factorization of n.
The Memory complexity of modified-sieve-algorithm (for factorization of integers) should be O(N), not O(N lgN).
(I used just 4 arrays of size 2000000, and used memory is almost 30000.
You shouldn't use more than 4 linear-arrays, or you'll get MLE.)
for each integer v ∈ [1...N],
store the prime factor factor[v] that divides v.
And, another hint :
factorization of 72 can refer factorization of 9, if factor[72] is 2.
The formula for phi(n) that uses the factorization of n is this if I am not mistaken: phi(n) = n*(1 - 1/p1)*....*(1- 1/pr) if the prime factors of n are p1, ... to pr. This can be rewritten as (n/p1...pr)*phi(p1)*...*phi(pr)
However my approach modifying the sieve and using this formula is still slow (about 1.2s on the OJ without I/O operations - I used 1 submission to time it and about 1.3s on my PC) as I am running the "full" sieve compared to those whose code run is < 1s
By "full" sieve I mean that I let the sieve continue after sqrt(2000000) which is about 1414 rather than let the sieve stop at 1414 so that all primes are handled. So my code is actually O(n^2) rather than O(n log n). It was mentioned in the above quote that it is possible to compute all phi(n) where n = 2000000 in O(n log n).
I used 3 arrays - 1 to store phi(n) for each n, one to store depthphi(n) fpr each n, and one to store sum(depthphi(i)) for i from 2 to n. the sum and depthphi are computed using DP and the bottleneck in my code is the code for computing phi(i).
I don't quite get the hints mentioned. Could someone give me a push in the right direction as to how to speed up my code? Thanks.
Posted: Thu Feb 23, 2006 5:28 pm
by wook
Do you know how it becomes O(N lgN)? Where the notation "lgN" comes from ?
For every integer K,
the number of prime factor(may same) that divides K is less than O(lgK).
More clearly,
e1 + e2 + e3 + .... < lgK, where integer factorization K = p1 ^ e1 + p2 ^ e2 + p3 ^ e3 + ....
Because, for example, the maximum number of prime factor is when K is power of 2.
Almost cases it is far less than lgK, so we gets O(NlgN).
Posted: Fri Feb 24, 2006 2:58 am
by chunyi81
I understand. It seems that I am doing 2 log k operations for each prime. For i = 1 and 2, phi = 1. Initializing for i >= 3, phi = i, I then use the sieve, if phi = i, then it's a prime, and I do a phi-- and then for each mutiple of i, I mutiply by phi(i)/i = (i - 1)/i = (1 - 1/i). This requires 1 multiplication and 1 division, which is why I have 2 log k. Is there a way to remove this constant 2?
Posted: Fri Feb 24, 2006 8:17 am
by wook
That's enough. The constant 2 is not so important.
If your implementation of this algorithms into source code is right, you will get accepted.
But when you want to make it faster, you need some optimizations.
The operation phi <- phi * (i - 1) / i takes 2 operations, one multiplication and one division,
which seems to be not able to reduced in just one operation, but there will be some other ways to improve your speed.
Good Luck.
Posted: Mon Feb 27, 2006 4:20 am
by chunyi81
Thanks. I already got AC in 1.201s and I don't think I can optimise it further.
Posted: Sat Mar 04, 2006 1:54 pm
by FAQ
Can someone help me why I got RE :'( It's ok with DevC++
Posted: Sat Mar 04, 2006 2:59 pm
by sumankar
Posted: Sat Mar 04, 2006 5:02 pm
by FAQ
Thank sumankar a lot, I got AC now
It's such a stupid mistake. I'm still a beginner with C++
Getting TLE
Posted: Sat May 20, 2006 7:23 am
by Ankur Jaiswal
Smbd plz help me optimize my code.
Here it is
Code: Select all
#include<stdio.h>
#include<math.h>
int prime[1414],pr_nums[300],cnt;
int dep[2000001],sodf[2000001];
void find_prime(){
int i,j,k;
for(i=0;i<1414;i++){
if(i%2==1)
prime[i]=1;
else
prime[i]=0;
}
pr_nums[0]=2;
for(i=3;i<38;i+=2){
if(prime[i]){
k=i*2;
for(j=i*i;j<1414;j+=k)
prime[j]=0;
}
}
pr_nums[1]=3;
cnt=1;
for(i=5;i<1414;){
if(prime[i]){
cnt++;
pr_nums[cnt]=i;
}
i+=2;
if(prime[i]){
cnt++;
pr_nums[cnt]=i;
}
i+=4;
}
}
void relatives(){
int i=0,ans,n,num;
long long srt;
for(n=2;n<=2000000;n++){
ans=num=n;
srt=(long long)sqrt(num);
for(i=0;pr_nums[i]<=srt && num!=1 && i<cnt;i++){
if(num%pr_nums[i]==0){
ans=(ans/pr_nums[i])*(pr_nums[i]-1);
while(num%pr_nums[i]==0)
num/=pr_nums[i];
}
}
if(num!=1)
ans=(ans/num)*(num-1);
if(ans==1)
dep[n]=1;
else
dep[n]=dep[ans]+1;
sodf[n]=sodf[n-1]+dep[n];
}
sodf[1]=0;
}
int main(){
find_prime();
relatives();
int n1,n2,t;
scanf("%d",&t);
while(t>0){
t--;
scanf("%d%d",&n1,&n2);
printf("%d\n",sodf[n2]-sodf[n1-1]);
}
return 0;
}
Posted: Sat May 20, 2006 10:33 am
by mamun
Read other posts. Forget about prime genearation. Try to use this method to find phi
for all i.
chunyi81 wrote:I understand. It seems that I am doing 2 log k operations for each prime. For i = 1 and 2, phi = 1. Initializing for i >= 3, phi = i, I then use the sieve, if phi = i, then it's a prime, and I do a phi-- and then for each mutiple of i, I mutiply by phi(i)/i = (i - 1)/i = (1 - 1/i). This requires 1 multiplication and 1 division, which is why I have 2 log k. Is there a way to remove this constant 2?
Posted: Sat May 20, 2006 12:36 pm
by Ankur Jaiswal
thats a great algorithm... going to implement it and i hope it wont give TLE.
thanx mamun (and ofcourse chunyi81).
Edited:
Got it accepted in around 2.1 secs.!!!
thanx a lot again.
Posted: Fri May 26, 2006 7:40 pm
by Ankur Jaiswal
I modified my code a bit and wow!!! got accepted in little over 1 sec. Now i am ranked 9th in this problem.