OJ Board

Posted: **Tue May 02, 2006 11:28 am**

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

Posted: **Thu Jul 20, 2006 2:44 pm**

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

Posted: **Tue Aug 08, 2006 6:50 pm**

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;
}

Posted: **Tue Aug 08, 2006 8:45 pm**

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

Posted: **Sun Sep 03, 2006 6:38 pm**

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.

Posted: **Sun Sep 03, 2006 6:56 pm**

Ok I got AC

i have a mistake

thanks to all

Posted: **Thu Jun 07, 2007 8:14 am**

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

Posted: **Thu Jun 07, 2007 2:56 pm**

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

Posted: **Sat May 03, 2008 2:34 am**

deleted after AC

Posted: **Sat May 03, 2008 2:56 pm**

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

Posted: **Sat May 03, 2008 6:48 pm**

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

Posted: **Sat Feb 14, 2009 10:05 pm**

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.

Posted: **Thu Sep 15, 2011 1:42 pm**

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

OJ Board

10299 - Relatives

GOT IT ACCEPTED

10299 relatives TLE

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

Tell me the Algo:

TLE!!

a better algo...plz...

Re: 10299 - WA(passes all dataset)

Re: 10299 - TLE on good algoritm please help

Re: 10299 - TLE on good algoritm please help

Re: 10299 - Relatives

Re: