## 10299 - Relatives

Moderator: Board moderators

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

### GOT IT ACCEPTED

thanx a lot everybody ... especially mamun
finally i got it accepted.

ayeshapakhi
Learning poster
Posts: 60
Joined: Sun Apr 16, 2006 7:59 pm

### 10299 relatives TLE

thanks .......
i got ac.
the isprime function was the culprit......
Last edited by ayeshapakhi on Mon Sep 25, 2006 8:14 pm, edited 1 time in total.

dontcry
New poster
Posts: 5
Joined: Sun Aug 06, 2006 9:55 pm

### 10299: Relatives. Runtime Error!! Help please!!

Hi, I get Runtime Error (Invalid Memory Reference) for this program and I still can't figure out why (or at least what it means). I was wondering if anyone could help me. Thanks a lot!

Code: Select all

``````//relatives

#include <iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>

using namespace std;

long long  n,r;
long long phi;
int main()

{
long long i;
vector<long long> esp(1000001,1);
esp[0]=esp[1]=0;
for (i=2;i<1000001;i++){
if (esp[i]==1) for (int j=2*i;j<1000001;j+=i) esp[j]=0;
}

while(cin>>n, n) {

phi=n;
i=2; r=0;
long long a; a=n;

while(n>1 || i<(sqrt(a)+1)) {

if (n%i!=0) {i++; while(!esp[i] && i<100000) {i++;}}

else {n=n/i;
if(r!=i) {phi=phi/i; phi=phi*(i-1);}
r=i;}
}

if(n>1) {phi=phi/n; phi=phi*(n-1);}

cout<<phi<<endl;

}

return 0;
}
``````

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:
It usually means that your array might be too small to handle some cases... for example you made an array with size 100000... but in some cases, your program points to index 100005, that's why you got Runtime Error (Invalid Memory Reference)...

Btw, your program failed in this case :
454545445

mohsincsedu
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:

### Tell me the Algo:

I also got TLE.

My algorithm:

a> generate prime number using seive up to lim = sqrt(1,00,000,000)
b> take an input N
c> res = 0
d> for i = 2,3,4,5,........lim. check if i is prime and N%i==0
d.1> res = res/i*(i-1)
d.2> do until N%i!=0
N/=i
e> if N not equal to 1
then res = res/n*(n-1);
f> print res and go to step b.

plz tell me the efficient algorithm..............

Amra korbo joy akhdin............................

mohsincsedu
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:
Ok I got AC
i have a mistake

thanks to all
Amra korbo joy akhdin............................

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

### TLE!!

my logic remained the same for problem 10179 as well as this problem...
but still it didnt work out here.... donno why...

my algo:

generate all the primes <=l sqrt(1000000000) using sieve

then taking an input number say N
sol=1
then finding the power of each of the primes P in N
and then multiplying sol by P^k-1 *(P-1)

it gives me TLE...
any suggestions in bettering my solution

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

### a better algo...plz...

hi.. Though I got this problem accepted.. I am sure from the CPU time it took ,that the solution can be much better .

first of all I am building a list of all primes less than sqrt(1000000000) using sieves..

then given a number N..
initialising sol=N
I am iterating though the list to find which ever divides N..
if a prime P divides N sol=(sol/P)*(P-1) and I repeatedly divide it with P till continues to do so exactly.... this repeated division is being done so as to end up with N=some prime >sqrt(1000000000) if at all N has one prime factor greater than sqrt(1000000000).

I guess this repeated division is one critical for the complexity of my code...

so can someone help me out by mentioning a way , I can avoid to do this repeated division...

kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Contact:

### Re: 10299 - WA(passes all dataset)

deleted after AC
Last edited by kbr_iut on Wed Sep 10, 2008 10:50 am, edited 1 time in total.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

Why did you add this line?

Code: Select all

``if(i>3401){phi=(phi/n)*(n-1);break;}``
Input:

Code: Select all

``````3403
0``````
Output:

Code: Select all

``3280``
Ami ekhono shopno dekhi...
HomePage

kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Contact:

thanx, now AC
actually I got the information from the board that if i>3401 in the for loop then the n is obviously to be a prime number.then i should only calculate phi over n....I dont know is it correct or not...or i misunderstood this...as soon as i delete that line I got AC....
how many many thanx to u...
while(acm){printf("U r utomost genious\n");
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Contact:

### Re: 10299 - Relatives

why Tle??
got accepted in 10179 with just changed,n=1 ans=1;
but here TLe.
my code.

Code: Select all

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

int main()

{
int x,count,flag,factor[32000],div_count;
double n;

while(scanf("%d",&x)==1)

{
if(x==0)
break;

if(x==1)
printf("0\n");

else

{
n=x;
div_count=1;
memset(factor,0,sizeof(factor));

while(x>1)

{

for( count=2 ;count<=sqrt(x);count++)

{

flag=1;

if(x%count==0)

{

if(factor[count]==0)
n=n*(1-(float)1/count);

factor[count]=1;
x=x/count;
//p_count=1;
div_count=0;;
break;
}

flag=0;

}

if((flag==0)|| sqrt(x)<2)

break;

}

if(div_count==1)

n=x-1;

else if(div_count==0)
{
if(x<32000 && factor[x]==0)
n=n*(1-(float)1/x);

else if(x>32000)
n=n*(1-(float)1/x);
}

printf("%.0lf\n",n);
}

}
return 0;

}

``````
plz some suggestion how to speed up.
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359

rahian
New poster
Posts: 5
Joined: Wed Jul 30, 2008 3:27 am
Location: CUET
Contact:

### Re:

makbet wrote:This program seems to work correctly for all inputs that I found here or made up.
But I constantly get WA
Thanks for any help

[c]#include <stdio.h>
#include <math.h>
int prime[100000];
int pl=0;
int sito(){
char p[100000];
int i,j;
p[1]=1;
p[2]=0;
for (i=2;i<=100000;++i)
if (!p)
for (j=2;j*i<100000;++j)
p[j*i]=1;
for (i=2;i<100000;++i)
if (!p)
prime[pl++]=i;
}
int main(){
long long i,n,q;
long long sn;
sito();
while (1){
scanf("%lld",&n);
if (!n) return 0;
if (n==1) { printf("0\n"); continue;}
q=n;
sn=rint(ceil(sqrt(n)));
/* printf("%d\n",sn);*/
for (i=0;prime<=sn ;++i)
if (n%prime==0){
/* printf("%d\n",prime);*/
q=q-q/prime;
while (n%prime==0) n/=prime;
}
if (n>1) q=q-q/n;
/* printf("%d\n",n);*/
printf("%lld\n",q);
}
return 0;
}[/c]

double q;
for (i=0;prime<=sn ;++i)
if (n%prime==0)
q= q*(1.00-(1.00/prime[i]))
/* Think Technically*/