## 10990 - Another New Function

Moderator: Board moderators

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of
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``````
Sorry For My Poor English..

mrahman
New poster
Posts: 25
Joined: Mon Oct 24, 2005 9:45 am
Contact:

### Recursion+DP to solve this Problem

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
Practice Makes a man perfect

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
No recursion, just a well coded sieve (but there's still plenty of room for improvements ).
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore
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.

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of
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).
Sorry For My Poor English..

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore
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?

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of
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.
Sorry For My Poor English..

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore
Thanks. I already got AC in 1.201s and I don't think I can optimise it further.

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm
Can someone help me why I got RE :'( It's ok with DevC++

Code: Select all

``````Aced
``````
Last edited by FAQ on Sat Mar 04, 2006 5:01 pm, edited 1 time in total.

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:
FAQ wrote:

Code: Select all

``[...] scanf("%d\n", t);``
should've been

Code: Select all

``scanf( "%d\n", &t );``

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm
Thank sumankar a lot, I got AC now
It's such a stupid mistake. I'm still a beginner with C++

Ankur Jaiswal
New poster
Posts: 31
Joined: Sat Apr 01, 2006 6:24 am
Contact:

### Getting TLE

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;
}
``````

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Contact:
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?

Ankur Jaiswal
New poster
Posts: 31
Joined: Sat Apr 01, 2006 6:24 am
Contact:
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.

Ankur Jaiswal
New poster
Posts: 31
Joined: Sat Apr 01, 2006 6:24 am
Contact:
I modified my code a bit and wow!!! got accepted in little over 1 sec. Now i am ranked 9th in this problem.