## 10299 - Relatives

Moderator: Board moderators

tetris
New poster
Posts: 2
Joined: Sun Sep 22, 2002 4:57 pm

### 10299 - Relatives

My code gets WA after rejudged.
Can anybody tell me what's your output for the following test case:
INPUT
1
2
3
4
5
6
7
8
9
10
123456789
987654321
1000000000
0

OUTPUT
0
1
2
2
4
3
6
4
6
5
121225
114414401
400000000

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan
0
1
2
2
4
2
6
4
6
4
82260072
619703040
400000000

tetris
New poster
Posts: 2
Joined: Sun Sep 22, 2002 4:57 pm

### What's wrong with this code?

Code: Select all

``````/* @JUDGE_ID: 17366JM 10299 C++ "" */
#include <iostream>
#include <cmath>
using namespace std;

int num;

void solve()
{
int i, result, cnt;

result = num;
for (i = 2; i <= (int)sqrt(num); i++) {
cnt = 0;
while (num % i == 0) {
num /= i;
cnt++;
}
if (cnt != 0) {
result = result * (i - 1) / i;
}
}
if (num != 1) {
result = result * (num - 1) / num;
}
cout << result << endl;
}

int main()
{
cin >> num;
while (num != 0) {
if (num == 1)
cout << 0 << endl;
else
solve();
cin >> num;
}
return 0;
}

``````

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

### Re: What's wrong with this code?

int overflow...

you can first divide then multiple
Last edited by Even on Sun Feb 09, 2003 8:51 am, edited 1 time in total.

RuiFerreira
New poster
Posts: 23
Joined: Mon Dec 16, 2002 8:01 pm
Location: Portugal
Contact:

### 10299

Hi!
i'm having troubles with this program!! whats wrong with my algorithm?

[c]
#include <stdio.h>
#include <ctype.h>
#include <math.h>

int main(void)
{

char linha;
int i,j,num,primos,p,flag,raiz,total;

/*prime number genarating*/

memset(primos,0,32000*sizeof(int));

for (i=2;i<179;i++)
if (primos==0)
for (j=2;j<32000/i;j++)
primos[i*j]=1;

for (i=2,j=0;i<32000;i++)
if (primos==0)
p[j++]=i;

while(1)
{
gets(linha);
num=0;
i=0;
while(isdigit(linha))
num=num*10+linha[i++]-'0';

if (num==0)
break;

/*determination of phi(num)*/

raiz=(int)sqrt(num);

flag=1;
total=num;

i=0;
while(p<=raiz)
{
if (num%p==0)
{
total=total-total/p;
flag=0;
}
i++;
}

if (flag)
total--;

printf("%d\n",total);

}

return 0;
}

[/c]

sorry but some of the variable names are in portuguese...

i've notest that the answer for the case 987654321 migth be wrong...

please help me Please visit my webpage!! I've got a lot of UVA statistics scripts
http://www.fe.up.pt/~ei01081/scripts/

mizocom2002
New poster
Posts: 3
Joined: Wed May 01, 2002 2:05 am

### 10299

i solved the problem and got it accepted and after rejudging i got time limit exceeded. here is the code
[cpp]
#include<iostream>
#include<cmath>
#include<fstream>
using namespace std;

int powerl(int,int);
bool primetest(int n);
int main()
{
//ofstream outs;
ifstream ins;
//outs.open("in.txt");
int n,count,div,index;
int prime;
int power;
bool flag;

cin>>n;
//test for primality

while(n!=0)
{
if(primetest(n))
cout<<n-1<<endl;
else{
div=2;
index=-1;
power=0;
flag=1;
count=1;
while(n!=1)
{
if(n%div==0)
{
n=n/div;
if(flag==1)
{index++;
power[index]=0;
}
prime[index]=div;
power[index]++;
flag=0;
}
else
{
div++;
flag=1;
}
}

for(int i=0;i<=index;i++)
{
count=count*(prime-1)*powerl(prime,power-1);
}
cout<<count<<endl;
if(count==0)
break;
}
cin>>n;
//for(int f=0;f<200000000;f++);
}
return 0;
}
int powerl(int n,int exponent)
{
int mult=1;
for(int i=1;i<=exponent;i++)
{
mult=mult*n;
}
return mult;
}
bool primetest(int n)
{
if(n%2==0)
return false;
for(int i=3;i<=sqrt(n);i+=2)
{
if(n%i==0)
return false;
}
return true;
}

[/cpp]
mizo

Learning poster
Posts: 73
Joined: Mon Oct 14, 2002 7:15 am
Location: United States
There are 2 reasons why you're getting TLE:

1) There is a faster method - you should give the problem more thought. 2) There some efficiencies in your code. If your previous time was something like 10.5 seconds then you have a chance of speeding this up enough to make the 10 second barrier.

In primetest(), you check divisibility by all the odd numbers, so you will check divisibility by 3, 9, 15, 21, ... (1/3rd of all the odd numbers), 5, 15, 25, 35, ... (1/5th of all the odd numbers), 7, 21, 35, ... (1/7th of all the prime numbers) etc. But to see if n is composite you really only need to check all the prime factors up to square root, not all the odd numbers. (And these primes should be precalculated with a sieve).

Your for loop condition in primetest() is slow: each iteration n is converted to a floating point value to pass into sqrt(), the sqrt() function runs, i is converted to a floating point value, and a comparision is done.

It is better is to precalculate and store non-trivial calculations like sqrt():
[cpp]
int squareRoot = static_cast< int >( sqrt( n ) );
for( int i = 3; i <= squareRoot; i += 2 ) {
// ...
}
[/cpp]
Or avoid them:
[cpp]
for( int i = 3; i * i <= n; i += 2 ) {
// ...
}
[/cpp]

powerl() is also slow - use pow() in math.h or use square and multiply algorithm:
[cpp]
// returns base ^ exp (possible overflow!)
unsigned int
myPow( unsigned int base, unsigned int exp ) {
unsigned int result( 1 );
unsigned int currentPower( base );

if( bitMask & exp ) {
result *= currentPower; // multiple
}
currentPower *= currentPower; // square
}

return result;
}
[/cpp]

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

### 10299 - TLE??

Is it possible for the code to get TLE?? Could someone help me??
[c]
#include<stdio.h>
#define MAX 15814v jm .,mc kjmjf
#define KEPT 1
#define DELETED 0
void main(void)
{
char *sieve;
int *prime,count,x,i,j,factor;
long n,temp;
sieve=(char *)malloc(sizeof(char)*MAX);
prime=(int *)malloc(sizeof(int)*3402);
for(x=0;x<MAX;x++)
sieve[x]=KEPT;
prime=2;
for(x=0,count=1;x<MAX;x++)
if(sieve[x]==KEPT)
{
i=2*x+3;
prime[count++]=i;
for(j=i+x;j<MAX;j+=i)
sieve[j]=DELETED;
}
free(sieve);
while(1)
{
scanf("%ld",&n);
if(!n)
break;
if(n==1)
{
printf("0\n");
continue;
}
for(x=0,count=0,temp=n;x<3402;x++)
if(temp%prime[x]==0)
{
factor[count++]=prime[x];
while(temp%prime[x]==0)
temp/=prime[x];
}
if(temp>1)
factor[count++]=temp;
for(x=0;x<count;x++)
n/=factor[x],n*=factor[x]-1;
printf("%ld\n",n);
}
free(prime);
}
[/c]

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan
Sorry...The 2nd line should be '#define MAX 15814'

ram
New poster
Posts: 30
Joined: Wed Mar 06, 2002 2:00 am
Contact:

### ur code

Hi,

If I am correct, u are doing a brute force here which would obviously lead to a TLE. U should use totient function.

Search for totient function at:

http://mathworld.wolfram.com

This is the best place for any math or number thoery problems.

good luck,
ram.

RuiFerreira
New poster
Posts: 23
Joined: Mon Dec 16, 2002 8:01 pm
Location: Portugal
Contact:

### What's wrong??

Sorry.. I cant undestand whats wrong with my code!!! can you help me?

[c]
#include <stdio.h>
#include <ctype.h>
#include <math.h>

int main(void)
{

char linha;
int i,j,num,primes,p,flag,sqroot,phi;

/*prime number genarating*/

memset(primes,0,32000*sizeof(int));

for (i=2;i<179;i++)
if (primes==0)
for (j=2;j<32000/i;j++)
primes[i*j]=1;

for (i=2,j=0;i<32000;i++)
if (primes==0)
p[j++]=i;

while(1)
{
scanf("%d",&num);
if (num==0)
break;

/*determination of phi(num)*/

sqroot=(int)sqrt(num);

flag=1;
phi=num;
i=0;
while(p<=sqroot)
{
if (num%p==0)
{
phi-=phi/p;
flag=0;
}
i++;
}
if (flag)
phi--;
/*output*/

printf("%d\n",phi);

}

return 0;
}
[/c]

I've noted that i've got a wrong answer to the input 987654321
Please visit my webpage!! I've got a lot of UVA statistics scripts
http://www.fe.up.pt/~ei01081/scripts/

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

### ...

987654321 = 3^2 x 17^2 x 379721

it has three prime factors 3, 17, 379721

your prime table only up to 32000.

in this case, you lost the last one prime 379721

987654321 * ( 1-1/3 ) * ( 1-1/17 ) = 619704672

987654321 * ( 1-1/3 ) * ( 1-1/17 ) * (1-1/379721 ) = 619703040

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

### Can samebody check this cases please?

I'm getting WA over and over again. So I would like that sameone check this cases to see were my code is wrong.

INPUT

1
2
3
4
5
6
7
8
9
10
123456789
987654321
1000000000
7
12
1000000
123124
123312
4444
1111
12123123
999999999
223092870
0

OUTPUT
0
1
2
2
4
2
6
4
6
4
82260072
619703040
400000000
6
4
400000
61560
35136
2000
1000
8055144
648646704
36495360
400000000
1600000000

Thanks

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan
You have 23 input, but 25 ouput??

btw, the first 23 ouput is correct

Fernandez Jose
New poster
Posts: 8
Joined: Wed Sep 18, 2002 2:10 am
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