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

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan

Post by Even » Fri Jun 27, 2003 4:06 am

Fernandez Jose wrote:Thanks for your answer. Sorry :oops: I got mixed up with the inputs. I add two more for cheking a possible overflow, they are:

INPUT:
1000000000
10000000001

OUTPUT:
400000000
1600000000
second one
9897840000

10000000001 = 101 x 3541 x 27961

Actually, the problem describes that n <= 1000000000,
so it will not have the second case 10000000001

but I think maybe your prime checker is something wrong with the bignum.

Fernandez Jose
New poster
Posts: 8
Joined: Wed Sep 18, 2002 2:10 am

Post by Fernandez Jose » Sat Jun 28, 2003 12:33 am

Thanks, I found the bug.

Now, I need to speed up my algorithm, I got TLE :x

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

10299

Post by Eduard » Tue Dec 30, 2003 11:33 pm

Can someone tell me a good algorithm for solving this problem.I can't solve it because n is very big help please.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

pavelph
Learning poster
Posts: 57
Joined: Wed Dec 10, 2003 7:32 pm
Location: Russia, Saint-Petersburg

Euler`s Function

Post by pavelph » Thu Jan 01, 2004 6:35 pm

First of all this is math problem.
f(n) - number of positive integers less than n are relatively prime to n.
This is Euler`s Function.
If n=(p1^a1)*(p2^a2)*...*(pk^ak) where p1, ..., pk - prime numbers than f(n)=n*(1-1/p1)*(1-1/p2)*...*(1-1/pk) .
I think it may help you.

howardcheng
Learning poster
Posts: 71
Joined: Thu Aug 21, 2003 1:56 am

10299: tricky input?

Post by howardcheng » Sat Jan 24, 2004 7:31 pm

I happen to know where this problem was originally used, and my solution works on the data set that was used at that time. But when I submit my solution to the online judge I just kept getting WA. I tried going to long long as well just in case there is an overflow (there shouldn't be one) and it didn't fix the problem. So what is the trick? (Yes, I know the Euler phi function.)

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

Post by Dmytro Chernysh » Sun Jan 25, 2004 1:25 am

The only one trick is for n=1 the answer is 0, not 1 :-)
I happen to know where this problem was originally used,
Cool... I know at least 30% of the origin of the Judge problems :D

One quick question -- are you the same Howard Cheng form Waterloo? :-)
I think yes... So, can we talk?

howardcheng
Learning poster
Posts: 71
Joined: Thu Aug 21, 2003 1:56 am

Post by howardcheng » Sun Jan 25, 2004 1:59 am

Thanks, that did the trick. I guess the original data never had n = 1, and my old "solution" worked at the time.

Yes, I was at Waterloo a while ago. Feel free to e-mail me (I'm at cheng@cs.uleth.ca now).

makbet
New poster
Posts: 44
Joined: Tue Nov 26, 2002 11:01 pm
Location: Wejherowo

Post by makbet » Tue Jan 27, 2004 3:57 pm

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]

matrix2
New poster
Posts: 19
Joined: Wed Jul 21, 2004 11:14 am
Location: Suceava, Romania
Contact:

10299 - TLE on good algoritm please help

Post by matrix2 » Sat Sep 25, 2004 7:16 pm

Hy!
I used the clasical algorithm to solve this problem, that means Euler phi function and I still get TLE. I don't know why..
please help me understand why...
Here goes my code:

Code: Select all

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

int main(void)
{
	int n, i, phi;
	while(scanf("%d", &n) == 1)
	{
		if(n == 0)
			break;
		phi = n;
		for(i = 2; i <= (int)sqrt(n); i++)
			if(n%i == 0)
			{
				phi = (phi / i) * (i-1);
				n /= i;
				while(n % i == 0)
					n /= i;
			}
		if(phi == n) /* n is prime */
			phi--;
		printf("%d\n", phi);
	}
	return 0;
}
Thank you for future answering.
Things are simple, but we make them complex.

matrix2
New poster
Posts: 19
Joined: Wed Jul 21, 2004 11:14 am
Location: Suceava, Romania
Contact:

Solved...

Post by matrix2 » Sun Sep 26, 2004 1:17 am

Lastly I've solved this problem. I've got TLE because of square() function which was evaluated every step in the for() loop. Also the above code would give WA even if we improve it.

Problem solution is easy as PI, because it's pure mathematic:
For a number n = p1^a1 * p2^a2 * . . . * pn^an, where p1,p2,..,pn are prime factors of n, the Euclidean function phi(n) = n*(1-1/p1)*(1-1/p2)*....*(1-1/pn) give us the number of relatively prime numbers to n which are positive and smaller than n.

Goodluck and thanx anyway!
Things are simple, but we make them complex.

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

10299 Relatives

Post by Antonio Ocampo » Sat Dec 18, 2004 6:49 am

Hi

I got TLE :-? . Please, could someone tell me how to improve my code???

Thanks in advance :wink:

Code: Select all


#include <iostream>
#include <cstdio>

using namespace std;

void main()
{
   int limite,n,i,sum;

   scanf("%i",&n);

   do
   {
       sum = n;
       limite=(int)sqrt(n);

       for (i=2;i<= limite;++i)
       {
         if (n%i == 0)
            sum -= sum/i;

         while (n%i == 0)
             n /= i;
       }

       if (n > 1)
        sum -= sum/n;

       cout<<sum<<"\n";

      scanf("%i",&n);
   }
   while (n);
}

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Sat Dec 18, 2004 11:54 am

Say, limite=10000.
There are only 1229 prime numbers in 1 to 10000, but your code are doing 10000 % operations. Certainly you should ignore compositie number.
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Mon Feb 28, 2005 3:04 pm

PHI(N) is called Euler Function :) and Not Euclidian Function.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Mon Feb 28, 2005 4:35 pm

For anyone who might need some sample I/O.

INPUT

Code: Select all

1
2
3
4
7
12
100
200
1001
1331
31991
999999
1000000
999999996
999999997
999999998
999999999
1000000000
0
OUTPUT

Code: Select all

0
1
2
2
6
4
40
80
720
1210
31990
466560
400000
333333328
985320000
499275720
648646704
400000000
Note that the output for N == 1 should be zero and not 1.

In the definition of the Euler Function PHI(N), normally
PHI(1) is defined as equal to 1.
It is the only degenerate case in the definition of PHI(N).

But here, in this problem, we really want to count the
positive integers which are smaller than N and which are
relatively prime to N.
As there're no smaller positive integers than 1 the answer
for 1 should be ZERO ( 0 ) and not ONE ( 1 )
( although ONE==PHI(ONE) ).

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Mon Feb 28, 2005 4:36 pm

For anyone who might need some sample I/O.

INPUT

Code: Select all

1
2
3
4
7
12
100
200
1001
1331
31991
999999
1000000
999999996
999999997
999999998
999999999
1000000000
0
OUTPUT

Code: Select all

0
1
2
2
6
4
40
80
720
1210
31990
466560
400000
333333328
985320000
499275720
648646704
400000000
Note that the output for N == 1 should be zero and not 1.

In the definition of the Euler Function PHI(N), normally
PHI(1) is defined as equal to 1.
It is the only degenerate case in the definition of PHI(N).

But here, in this problem, we really want to count the
positive integers which are smaller than N and which are
relatively prime to N.
As there're no smaller positive integers than 1 the answer
for 1 should be ZERO ( 0 ) and not ONE ( 1 )
( although ONE==PHI(ONE) ).

Post Reply

Return to “Volume 102 (10200-10299)”