10179 - Irreducible Basic Fractions

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

Moderator: Board moderators

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:

Post by Minilek » Sun Aug 08, 2004 5:24 am

A number can have a prime factor greater than its sqrt.
That's ok. You only need to generate primes up to sqrt(1 billion)
to test primality efficiently. For primes bigger than the sqrt, just
loop through the primes less than the sqrt and see if any of them
divide it. If not, it must be prime. I used this method for AC in 0.154.

rbarreira
New poster
Posts: 5
Joined: Sun Oct 03, 2004 12:14 am

Post by rbarreira » Tue Oct 05, 2004 9:59 pm

I had the same problem in 10179. Fixing the special case for the input "1" gave me AC :)

But I don't really understand why the output in that case should be 1, since in the example given in the problem text, they don't count 0/12 as a irreducible basic fraction... Isn't this inconsistent?

Piers Kennedy
New poster
Posts: 3
Joined: Thu Apr 22, 2004 8:12 pm

Post by Piers Kennedy » Thu Oct 14, 2004 6:52 pm

[..in the example given in the problem text, they don't count 0/12 as a irreducible basic fraction..]

That is correct 0/12 can be reduced to any fraction with a non-zero denominator (e.g.0/1 etc.)

Problem 10179 differs from 10299 in that when n=1 there is an allowable irreducible fraction of 1/1 giving a count of 1.

In 10299 the problem description asks for the number of positive integers less than n which are relatively prime to n. For n=1 this is 0. Interestingly the EulerPhi function in Mathematica returns 1 for n=1!

[/quote]

athlon19831
New poster
Posts: 20
Joined: Thu Jan 19, 2006 2:32 pm

10179 Time Limit Exceeded

Post by athlon19831 » Wed Feb 01, 2006 4:01 pm

#include "iostream.h"
#include "stdio.h"
#include "string.h"
#include "math.h"

bool Gcd(long M,long N)
{
long Rem;
while(N>0)
{
Rem=M%N;
M=N;
N=Rem;
}
if(M==1)
return true;
else
return false;
}

int main(int argc, char* argv[])
{
long n;
long i,j;
long num;

while(cin>>n)
{
if(n==0)
break;
else
{
num=0;
for(i=0;i<n;i++)
{
if(Gcd(n,i))
{
num++;
}
}
cout<<num<<endl;
}
}
return 0;
}

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Wed Feb 01, 2006 5:24 pm

Test your program with the maximum input, 999999999. You'll feel the speed of your program.

Find Euler's Phi function.

szwesley001
New poster
Posts: 1
Joined: Wed Apr 05, 2006 9:54 pm
Location: Bauru
Contact:

10179 Time Limit Exceeded

Post by szwesley001 » Wed Apr 05, 2006 9:57 pm

Why?

/* @BEGIN_OF_SOURCE_CODE */

#include <stdio.h>
#define MAX 1000

int main()
{
unsigned long int m,n,x,vet[MAX]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
long int j=0,i=0;
float result1=0,fator=0;
long int r;
while(scanf("%ld",&m)==1)
{
if ((m>1000000000)||(m==0)) return 0;
x=2;n=m;i=0;
while (n>1)
{
r=n%x;
if (r==0)
{
if (x != vet)
{
i++;
vet=x;
}
n=n/x;
}
else if (n==x)
break;
else
x++;
}
result1 = m;
for (j=1;j<=i;j++)
{
fator=1;
fator/=vet[j];
result1 *= (1-fator);
}
printf("%ld\n",( unsigned long int)result1);
}
return 1;
}

/* @END_OF_SOURCE_CODE */
Wesley

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha » Wed Apr 05, 2006 11:40 pm

You post in the wrong Volume. see

http://online-judge.uva.es/board/viewto ... ght=10179

and before making a new subject, search in froum.

sohel_acm
New poster
Posts: 8
Joined: Fri May 19, 2006 11:27 pm
Location: Bangladesh

10179!!!! WA!!!Plz Help

Post by sohel_acm » Mon May 22, 2006 4:26 pm

Hi Solvers,
I am getting wa in 10179.But I can't find the bug in my code.Plz someone help me.Here is my code

Code: Select all

Deleted after getting ACC.
Thanx in advance.
Last edited by sohel_acm on Tue May 23, 2006 11:18 am, edited 1 time in total.
Love programmers,help programmers.

sohel_acm
New poster
Posts: 8
Joined: Fri May 19, 2006 11:27 pm
Location: Bangladesh

Post by sohel_acm » Tue May 23, 2006 11:16 am

I have found my error.At last I got ACC.
Love programmers,help programmers.

rhsumon
New poster
Posts: 48
Joined: Wed Aug 23, 2006 12:29 pm
Location: Dhaka

Re: 10179 - Irreducible Basic Fractions

Post by rhsumon » Wed Aug 20, 2008 10:20 pm

WA plz help
first time TLE then WA where is the wrong

Code: Select all

#include<stdio.h>
#include<math.h>
#include<stdlib.h>

#define P 100000

long prime[P]; 
long p[50000]; 
int phi[P+100];

void gen_prime(){
	int i,j;
	prime[0] = prime[1] = 1;
	for(i=2; i<=(long)sqrt(P); i++){
		if(prime[i]==0){ 
			for(j=i*i; j<=P-1; j=j+i){
				prime[j]=1;
			}
		}
	} 
	j=0; 
	for(i=0; i<=P-1; i++){ 
		if(prime[i] == 0){
			p[j++] = i;
		}
	}
}

void phgen(){
	int i,j;
    for(i=2;i<=P;i++)
        phi[i]=i;
	for(i=2;i<=P;i++){
        if(!prime[i]){
            for(j=i;j<=P;j+=i)
                phi[j]-=phi[j]/i;
		}
	}
}

int is_prime(int a){
	int i;
	for(i=0; p[i]*p[i]<=a; i++){
		if(a%p[i]==0) return 0;
	}
	return 1;
}

int main()
{
	gen_prime();
	phgen();
	int n,pi,i,flag;
	while(scanf("%d",&n)==1 && n){
		if(n==1) printf("1\n");
		else if(n <= P) printf("%d\n",phi[n]);
		else{
			if(is_prime(n)) printf("%d\n",n-1);
			else{
				pi=1;
				for(i=0; n!=1&&p[i]*p[i]<=n; i++){
					flag=0;
					while(n%p[i]==0){
						pi*=p[i];	
						n/=p[i];
						flag=1;
					}
					if(flag==1) pi-=pi/p[i];
					if(is_prime(n)&&n>1){
						pi*=(n-1);
						break;
					}
				}
			}
			printf("%d\n",pi);
		}
	}
	return 0;
}


stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Re: 10179 - Irreducible Basic Fractions

Post by stcheung » Mon Oct 06, 2008 8:16 am

Your program outputs an extra line for primes larger than 100000. Try it with 100003.

Taman
New poster
Posts: 32
Joined: Sun Oct 11, 2009 8:59 pm
Location: Southeast University

Re: 10179 - Irreducible Basic Fractions

Post by Taman » Fri Jan 01, 2010 2:20 pm

Well, I think output for 1 is 1.
because, my compiler shows gcd(0,1) = 1 and the problem statement states,
A fraction m / n is basic if 0 <= m < n and it is irreducible if gcd(m, n) = 1.
I am to mention that I use Euclid's algorithm like others to find gcd(m,n).

So, i think (0,1) is considered to be an irreducible fraction in this sense and this helped me to get acc quite on the first submission. . . .looking for your further correction :D.

Pro.metal
New poster
Posts: 9
Joined: Fri Dec 17, 2010 8:13 pm

Re: 10179 - Irreducible Basic Fractions

Post by Pro.metal » Thu Mar 31, 2011 1:43 pm

When i run the loop upto sqrt(n) i get WA because not all the prime factors are below sqrt(n) for example 123456.
But when i do it upto n/2, i get TLE. Please help. Thanks

Code: Select all

#include <stdio.h>
#include <math.h>
char prime[1000000000];
int main()
{
	long long n,prod,i,j,k;
	long long d;
	for(i=2; i<10000; i+=2)
	{
        if(prime[i]==0)
        {
            for(j=i*i; j<10000000; j+=i) prime[j] = 1;
        }
        if(i==2) i = i - 1;  
    }
    while(scanf("%lld",&n)!=EOF)
    { 
        if(!n) break;
        prod = n;
        for(k=2; k<n/2; k++) 
        {
            if(n%k==0 && !prime[k])
            {
                prod = prod *(k-1) / k;
            }     
        }              
        printf("%lld\n",prod);
	}
	return 0;
}  


DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 10179 - Irreducible Basic Fractions

Post by DD » Fri Apr 01, 2011 10:39 pm

Taman wrote:Well, I think output for 1 is 1.
because, my compiler shows gcd(0,1) = 1 and the problem statement states,
A fraction m / n is basic if 0 <= m < n and it is irreducible if gcd(m, n) = 1.
I am to mention that I use Euclid's algorithm like others to find gcd(m,n).

So, i think (0,1) is considered to be an irreducible fraction in this sense and this helped me to get acc quite on the first submission. . . .looking for your further correction :D.
Thanks for this suggestion, I got several W.As due to this case :oops:
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

Post Reply

Return to “Volume 101 (10100-10199)”