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

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

10299 - Relatives

Post by tetris » Sun Sep 22, 2002 5:04 pm

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

Post by Even » Sun Sep 22, 2002 8:46 pm

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?

Post by tetris » Mon Sep 23, 2002 4:59 am

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?

Post by Even » Mon Sep 23, 2002 4:08 pm

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

Post by RuiFerreira » Mon Dec 16, 2002 8:07 pm

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[20];
int i,j,num,primos[32000],p[3445],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)
{
/*input reading*/
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

Post by mizocom2002 » Mon Jan 06, 2003 3:34 am

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[100000];
int power[100000];
bool flag;

cin>>n;
//test for primality

while(n!=0)
{
if(primetest(n))
cout<<n-1<<endl;
else{
div=2;
index=-1;
power[0]=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

rjhadley
Learning poster
Posts: 73
Joined: Mon Oct 14, 2002 7:15 am
Location: United States

Post by rjhadley » Tue Jan 07, 2003 12:12 am

There are 2 reasons why you're getting TLE:

1) There is a faster method - you should give the problem more thought. :D

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 bitMask( 1 );
unsigned int currentPower( base );

for( unsigned int bitMask = 1; bitMask <= exp; bitMask <<= 1 ) {
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??

Post by htl » Wed Jan 29, 2003 2:08 pm

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[3403];
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[0]=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

Post by htl » Wed Jan 29, 2003 2:15 pm

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

Post by ram » Mon Feb 03, 2003 1:05 am

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

Post by RuiFerreira » Sat Feb 08, 2003 12:09 am

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[20];
int i,j,num,primes[32000],p[3500],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)
{
/*input reading*/
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

...

Post by Even » Sun Feb 09, 2003 8:50 am

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

and your answer become

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

and the correct answer is

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?

Post by Fernandez Jose » Thu Jun 26, 2003 1:28 pm

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

Post by Even » Thu Jun 26, 2003 4:11 pm

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

Post by Fernandez Jose » Thu Jun 26, 2003 7:00 pm

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

Post Reply

Return to “Volume 102 (10200-10299)”