10990 - Another New Function

wook · Post by **wook** » Tue Feb 14, 2006 5:18 am

A simple one :

input

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

mrahman · Post by **mrahman** » Thu Feb 16, 2006 9:08 am

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

Krzysztof Duleba · Post by **Krzysztof Duleba** » Thu Feb 16, 2006 10:08 am

No recursion, just a well coded sieve (but there's still plenty of room for improvements

).

chunyi81 · Post by **chunyi81** » Thu Feb 23, 2006 1:20 pm

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 · Post by **wook** » Thu Feb 23, 2006 5:28 pm

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).

chunyi81 · Post by **chunyi81** » Fri Feb 24, 2006 2:58 am

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 · Post by **wook** » Fri Feb 24, 2006 8:17 am

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.

chunyi81 · Post by **chunyi81** » Mon Feb 27, 2006 4:20 am

Thanks. I already got AC in 1.201s and I don't think I can optimise it further.

FAQ · Post by **FAQ** » Sat Mar 04, 2006 1:54 pm

Can someone help me why I got RE :'( It's ok with DevC++

Code: Select all

Aced

sumankar · Post by **sumankar** » Sat Mar 04, 2006 2:59 pm

FAQ wrote:
Code: Select all
[...] scanf("%d\n", t);

should've been

Code: Select all

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

FAQ · Post by **FAQ** » Sat Mar 04, 2006 5:02 pm

Thank sumankar a lot, I got AC now
It's such a stupid mistake. I'm still a beginner with C++

Ankur Jaiswal · Post by **Ankur Jaiswal** » Sat May 20, 2006 7:23 am

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 · Post by **mamun** » Sat May 20, 2006 10:33 am

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 · Post by **Ankur Jaiswal** » Sat May 20, 2006 12:36 pm

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 · Post by **Ankur Jaiswal** » Fri May 26, 2006 7:40 pm

I modified my code a bit and wow!!! got accepted in little over 1 sec. Now i am ranked 9th in this problem.

OJ Board

10990 - Another New Function

Recursion+DP to solve this Problem

Getting TLE