## 10299 - Relatives

Moderator: Board moderators

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan
Fernandez Jose wrote: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
New poster
Posts: 8
Joined: Wed Sep 18, 2002 2:10 am
Thanks, I found the bug.

Now, I need to speed up my algorithm, I got TLE Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

### 10299

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

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

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

### 10299: tricky input?

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
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
Learning poster
Posts: 71
Joined: Thu Aug 21, 2003 1:56 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
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;
int pl=0;
int sito(){
char p;
int i,j;
p=1;
p=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:

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

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

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

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
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:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
PHI(N) is called Euler Function and Not Euclidian Function.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
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
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
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) ).