10299 - Relatives

[Even]

Thanks for your answer. Sorry 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]

Thanks, I found the bug.

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

[Eduard]

Can someone tell me a good algorithm for solving this problem.I can't solve it because n is very big help please.

[pavelph]

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]

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]

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

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

[howardcheng]

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]

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]

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.

[matrix2]

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!

[Antonio Ocampo]

Hi

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

Thanks in advance

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

[..]

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.

[Sedefcho]

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

[Sedefcho]

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

[Sedefcho]

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