Page **2** of **4**

Posted: **Fri Jun 27, 2003 4:06 am**

by **Even**

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.

Posted: **Sat Jun 28, 2003 12:33 am**

by **Fernandez Jose**

Thanks, I found the bug.

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

### 10299

Posted: **Tue Dec 30, 2003 11:33 pm**

by **Eduard**

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

### Euler`s Function

Posted: **Thu Jan 01, 2004 6:35 pm**

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

### 10299: tricky input?

Posted: **Sat Jan 24, 2004 7:31 pm**

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

Posted: **Sun Jan 25, 2004 1:25 am**

by **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?

Posted: **Sun Jan 25, 2004 1:59 am**

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

Posted: **Tue Jan 27, 2004 3:57 pm**

by **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]

### 10299 - TLE on good algoritm please help

Posted: **Sat Sep 25, 2004 7:16 pm**

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

### Solved...

Posted: **Sun Sep 26, 2004 1:17 am**

by **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!

### 10299 Relatives

Posted: **Sat Dec 18, 2004 6:49 am**

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

Posted: **Sat Dec 18, 2004 11:54 am**

by **..**

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.

Posted: **Mon Feb 28, 2005 3:04 pm**

by **Sedefcho**

PHI(N) is called Euler Function

and Not Euclidian Function.

Posted: **Mon Feb 28, 2005 4:35 pm**

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

Posted: **Mon Feb 28, 2005 4:36 pm**

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