11424 - GCD - Extreme (I)

All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Post by Robert Gerbicz » Wed Mar 19, 2008 11:28 am

f74956227 wrote:Thank you Robert, i get ac now :D with 3.75 second, i saw your 0.050 rank...
it is so fast...

^^ thank for your hints! :P
Those are different, faster methods for 11424/11426.

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
Location: (CSE,DU) Dhaka,Bangladesh

Post by turcse143 » Thu Mar 20, 2008 9:20 pm

Robert i use ur method & got AC in 11424 but TLE in 11426
here is my code:

Code: Select all

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>

int MAX=4000001;
int *eular;
int *a; 
int fi(int n) 
     { 
       int result = n,i; 
       for(i=2;i*i <= n;i++) 
       { 
         if (n % i == 0) result -= result / i; 
         while (n % i == 0) n /= i; 
       } 
       if (n > 1) result -= result / n; 
       return result;
     }
main()
{
	int i,j,n;
	eular=(int*) (malloc) ((MAX+1)*sizeof(int));
	a=(int*) (malloc) ((MAX+1)*sizeof(int));
	for(i=1;i<MAX;i++)
		eular[i]=fi(i);
	memset(a,0,MAX*sizeof(int));
	for(i=1;i<MAX;i++)
		for(j=2*i;j<MAX;j+=i)
			a[j]+=i*eular[j/i];

	for(i=2;i<MAX;i++)
		a[i]+=a[i-1]; 
	freopen("11426.in","rt",stdin);
	while(scanf("%d",&n)==1)
	{
		if(n==0)
			break;
		printf("%d\n",a[n]);
	}
}
whats my problem? ples help
''I want to be most laziest person in the world''

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Thu Mar 20, 2008 9:34 pm

your euler phi generation is too much costly, try something like sieve.

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Post by Robert Gerbicz » Thu Mar 20, 2008 11:03 pm

emotional blind wrote:your euler phi generation is too much costly, try something like sieve.
And the type of "a" array should be long long int for problem 11426 and printf("%lld\n",a[n]);

kjus
New poster
Posts: 3
Joined: Sun Oct 22, 2006 6:59 pm

Post by kjus » Mon Mar 24, 2008 1:54 am

Robert Gerbicz wrote: Those are different, faster methods for 11424/11426.
Hello,

Would it be possible to have some hints about your faster method for this problem ?
I use sieving to compute the values of the phi function, and sieve as well (as you described above) to compute sum(i=1,n-1, gcd(i,n)) for n=1..N, so my total time complexity is O(N log N). (I got AC for 11426 in 4 seconds..)

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Mon Mar 24, 2008 2:05 am

kjus wrote:
Robert Gerbicz wrote: Those are different, faster methods for 11424/11426.
Hello,

Would it be possible to have some hints about your faster method for this problem ?
I use sieving to compute the values of the phi function, and sieve as well (as you described above) to compute sum(i=1,n-1, gcd(i,n)) for n=1..N, so my total time complexity is O(N log N). (I got AC for 11426 in 4 seconds..)
I submitted the same code for both 11424/11426. If we don't count the precomputation, my code is is O(sqrt(n)) for each input n.

pradeepr
New poster
Posts: 21
Joined: Fri May 25, 2007 11:52 am
Location: India

Re: 11424 - GCD Extreme (I)

Post by pradeepr » Sat Apr 26, 2008 3:43 pm

Hi,I tried to solve 11424/11426 in the same way as discussed in this section.I got accepted for 11424 but TLE for 11426.I am generating primes using sieves and then incorporating them to generate phi function.I am unable to make out where I am going wrong in11426.Please help me out..

Code: Select all

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
int main()
{
        int limit=2000;
        vector<bool> V(limit,true);
        vector<int> primes;
        vector<int> phi(4000001,0);
        vector<unsigned long long> g(4000001,0);
        V[0]=V[1]=false;
        for(int i=2;i<=limit;i++)
        {
                if(V[i])
                {
                        primes.push_back(i);
                        int reach;
                        for(int j=i;(reach=i*j)<limit;j++)           //prime number generation using sieves
                        {
                                V[reach]=false;
                        }
                }

        }
        phi[0]=phi[1]=0;
        phi[2]=1;
        for(int i=3;i<=4000000;i++)
        {
                phi[i]=i;
                int count=i;
                int size=primes.size();
                for(int j=0;j<size && primes[j]*primes[j] <=count;j++)
                {
                        if(count%primes[j]==0)
                        {
                                phi[i]=(phi[i]/primes[j])*(primes[j]-1);        //calculation of phi using primes generated through sieves.
                                while(count%primes[j]==0)
                                {
                                        count/=primes[j];
                                }
                        }
                }
                if(count!=1)
                {
                        phi[i]=(phi[i]/count)*(count-1);
                }
        }

        for(int i=1;i<=4000000;i++)
        {
                for(int j=2;j*i<=4000000;j++)
                {
                        g[j*i]+=i*phi[j];
                }

        }
        for(int i=2;i<=4000000;i++)
        {
                g[i]+=g[i-1];
                cout<< i<<' '<<g[i]<<'\n';
        }
        int N;
        while(cin >>N)
        {
                if(N==0)
                        return(0);
                else
                        cout<<g[N]<<'\n';
        }
        return(0);

}


Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 11424 - GCD Extreme (I)

Post by Obaida » Sun May 25, 2008 10:19 am

There is a problem in my code it's not breaking in n=0; but returns Debug Error!.
Can some one explain why this happens and how I can get out of this.
This is my while loop:

Code: Select all

while(scanf("%d",&N)==1&&N!=0)
{
	printf("%ld\n",gcd[N]);
}
I used Robert Gerbiczs formula and My time limit is good now .150 :cry:
try_try_try_try_&&&_try@try.com
This may be the address of success.

Samiul
New poster
Posts: 36
Joined: Thu Dec 13, 2007 3:01 pm

Re: 11424 - GCD Extreme (I)

Post by Samiul » Sun May 25, 2008 11:03 am

Your problem is not in this part of your code. I guess it could be array overrun.

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 11424 - GCD Extreme (I)

Post by Obaida » Sun May 25, 2008 11:39 am

But I think I am getting right answer for all the input sets. For this problem I am getting WA.
try_try_try_try_&&&_try@try.com
This may be the address of success.

Samiul
New poster
Posts: 36
Joined: Thu Dec 13, 2007 3:01 pm

Re: 11424 - GCD Extreme (I)

Post by Samiul » Sun May 25, 2008 4:36 pm

In my VS2005 compiler sometimes i get debug error for array overrun when the code finishes.

Post Reply

Return to “Volume 114 (11400-11499)”