Those are different, faster methods for 11424/11426.f74956227 wrote:Thank you Robert, i get ac nowwith 3.75 second, i saw your 0.050 rank...
it is so fast...
^^ thank for your hints!
11424 - GCD - Extreme (I)
Moderator: Board moderators
-
- Experienced poster
- Posts: 196
- Joined: Wed May 02, 2007 10:12 pm
- Location: Hungary, Pest county, Halasztelek
- Contact:
-
- Learning poster
- Posts: 81
- Joined: Wed May 09, 2007 9:59 pm
- Location: (CSE,DU) Dhaka,Bangladesh
Robert i use ur method & got AC in 11424 but TLE in 11426
here is my code:
whats my problem? ples help
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]);
}
}
''I want to be most laziest person in the world''
- emotional blind
- A great helper
- Posts: 383
- Joined: Mon Oct 18, 2004 8:25 am
- Location: Bangladesh
- Contact:
-
- Experienced poster
- Posts: 196
- Joined: Wed May 02, 2007 10:12 pm
- Location: Hungary, Pest county, Halasztelek
- Contact:
Hello,Robert Gerbicz wrote: Those are different, faster methods for 11424/11426.
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.kjus wrote:Hello,Robert Gerbicz wrote: Those are different, faster methods for 11424/11426.
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..)
Re: 11424 - GCD Extreme (I)
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);
}
Re: 11424 - GCD Extreme (I)
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:
I used Robert Gerbiczs formula and My time limit is good now .150 
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]);
}

try_try_try_try_&&&_try@try.com
This may be the address of success.
This may be the address of success.
Re: 11424 - GCD Extreme (I)
Your problem is not in this part of your code. I guess it could be array overrun.
Re: 11424 - GCD Extreme (I)
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.
This may be the address of success.
Re: 11424 - GCD Extreme (I)
In my VS2005 compiler sometimes i get debug error for array overrun when the code finishes.