10299 - Relatives

[tetris]

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]

0
1
2
2
4
2
6
4
6
4
82260072
619703040
400000000

[tetris]

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]

int overflow...

you can first divide then multiple

[RuiFerreira]

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

[mizocom2002]

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]

[rjhadley]

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

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]

Sorry...The 2nd line should be '#define MAX 15814'

[ram]

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]

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

[Even]

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]

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]

You have 23 input, but 25 ouput??

btw, the first 23 ouput is correct

[Fernandez Jose]

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