10299 - Relatives

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

Moderator: Board moderators

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

GOT IT ACCEPTED

Post by Ankur Jaiswal »

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

Post by ayeshapakhi »

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!!

Post by dontcry »

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:

Post by jan_holmes »

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:

Post by mohsincsedu »

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


thanks in advanced.
Amra korbo joy akhdin............................

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

Post by mohsincsedu »

Ok I got AC :D
i have a mistake

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

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

TLE!!

Post by pradeepr »

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

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

a better algo...plz...

Post by pradeepr »

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
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

Re: 10299 - WA(passes all dataset)

Post by kbr_iut »

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
Location: Dhaka, Bangladesh
Contact:

Re: 10299 - TLE on good algoritm please help

Post by Jan »

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
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

Re: 10299 - TLE on good algoritm please help

Post by kbr_iut »

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

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

Re: 10299 - Relatives

Post by sazzadcsedu »

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
For Hints: http://salimsazzad.wordpress.com

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

Re:

Post by rahian »

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*/

Post Reply

Return to “Volume 102 (10200-10299)”