10299 - Relatives

[Ankur Jaiswal]

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

[ayeshapakhi]

thanks .......
i got ac.
the isprime function was the culprit......

[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]

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]

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.

[mohsincsedu]

Ok I got AC
i have a mistake

thanks to all

[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]

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]

deleted after AC

[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

[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");

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

[rahian]

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