10042 - Smith Numbers

[zprian]

HI WR!! I OBTAINED AN ACCEPT!!!jejeje
I change the loop, and I check each number and use long, and now my program is ACCEPT!!!
thanks very much for all!!!

[Rocky]

Thanks For I/O
I Got ACC Now.I forgot To Post

Thank's

Rocky

[asif_rahman0]

Hello can anybody plz help me to understand the problem 10042?

[Mohammad Mahmudur Rahman]

At first make sure what a smith number is. By definition - Smith number is such a number that the sum of its digits is equal to the sum of digits of all it's prime factors (considering frequency). Let's consider the example given in the problem.
4937775 can be written as 3 * 5 * 5 * 65837 - which are it's prime factors.
Now, if you sum the digits of the original number, you get (4 + 9 + 3 + 7 + 7 + 7 + 5) = 42. Again summing the digits of the prime factors leads to -> {(3) + (5) + (5) + (6 + 5 + 8 + 3 + 7)} = 42. As both the sums are equal, 4937775 is a smith number.

Now, if you check the sample input, you will find 4937774 is not a smith number. Increment the number by one until you get a smith number which is the immediate next one in this case.

Similarly, if the input is 105, it's not a smith number and 106,107,108....,120 - none of these are smith #. The first smith # after 105 is 121. This will be your output. Hope it helps.

[asif_rahman0]

Thanks Mahmudur Bhai for your help.I now understand the problem and get ready for code.

[Pasa Yildirim]

Hello!

I have problems with my program . Can anybody tell me what's wrong in the code. I use algorithm from Programming Challenges.

Code: Select all

// 10042: Smith numbers

#include <cmath>
#include <iostream>
using namespace std;

typedef unsigned long inte;

inte sum (inte n)
{
	inte r = 0;	
	while (n)
	{
		r += n % 10;
		n /= 10;
	}
	return 0;
}

// This algorithm is from Programming challenges, 
// it works for me in other ACM problems
inte ptr (inte w)
{
	inte n = w;
	inte rez = 0;
	
	while (n % 2 == 0)
	{
		rez += 2;
		n /= 2;
	}
	
	inte i = 3;
	while (i <= (sqrt(n) + 1))
	{
		if (n % i == 0)
		{
			rez += sum(i);
			n /= i;
		}
		else i += 2;
	}
	
	if (n > 1) rez += sum(n);
	
	// If n == w ==> n is prime 
	if (n == w) return false;
	
	if (sum(w) == rez) return true;
	return false;
}

int main (void)
{	
	inte t; cin >> t;
	
	while (t--)
	{
		inte n; cin >> n;
		while (!ptr(++n));
		cout << n << endl;
	}
	
//	system("pause");
	return 0;
}

[chunyi81]

You made a very careless mistake in your code. I refer you to this part of your code:

Code: Select all

inte sum (inte n) 
{ 
   inte r = 0;    
   while (n) 
   { 
      r += n % 10; 
      n /= 10; 
   } 
   return 0; 
} 

This sum function is always returning 0. I think you meant return r.

[Pasa Yildirim]

chunyi81, thank you very much, i've got AC.
I don't even think that my mistake is so obivious
Thank you once more

[Masud]

I dont know why judge give me wrong answer
My code is given below...
What is the problem of it...

Code: Select all

#include<stdio.h>
#include<math.h>


long long int DigSum(long long int t)
{
 long long int m=0;
 while(t)
	{
     m+=t%10;
	 t/=10;
	}
 return m;
}

long long int PrimeFactorSum(long long int t)
{
 long long int k=0,i,d;
 while(t%2==0)
	{
	 k+=2;
	 t/=2;
	}
  d=sqrt(t);
 for(i=3;i<=d;i+=2)
	{
	 if(t%i==0)
		{
		 while(t%i==0)
			{
			k+=DigSum(i); 
			t/=i;
			}
		 d=sqrt(t);
		}
	}
 if(t>=i)k+=DigSum(t);
 return k;
}



void main()
{
 long cas;
 long long int sum1,sum2,n;
 scanf("%ld",&cas);
 while(cas--)
	{
	 scanf("%lld",&n);
	 while(0==0)
		{
		 sum1=DigSum(n);
	     sum2=PrimeFactorSum(n);
		 if(sum1==sum2)break;
	     else n++;
		}
	 printf("%lld\n",n);

	}
}

[mamun]

Read the question carefully

For every input value n, you are to compute the smallest Smith number which is larger than n.
...prime number is not worth being a Smith number...

Always search the forum for existing threads about your topic and use them if necessary instead of creating a new one. I'm sure you'll find a lot more help along with some test I/O if you search.

[rieo]

hi,

in 10042 smith numbers, i try the all input from other topic and get correct answer use gcc.

but when i submit my code, it gets signal 11 (SIGSEGV). Meaning:
Invalid memory reference

but i don't know in what condition could make this mistake


is there anyone can help me? thx.

[jan_holmes]

It is possibly because of your program tried to access the invalid memory, for example if you write the code like this :

Code: Select all

int arr[1000];
arr[1001] = 5;
printf("%d\n",arr[1001]);

It might be error, because you made an array with capacity only 1000 but you tried to access the 1002nd array... (0 is the 1st array).

[rieo]

if my array is : int prime[20000]; and i write a function
int digitsum(unsigned long int a)

then i write
psum+=digitsum(prime);
could make SIGSEGV ?

or unsigned long int s
but s=s%prime or s/=prime
could make SIGSEGV ?

because i test all data from 0 - 10^9 in gcc and all answer is fine

but when i submit... get SIGSEGV

[sumankar]

Maybe its time you posted the code in its entirety.
--
Suman
My Blog
My Web Page

[rieo]

finally i get accept, i found the bug is i use store primes which are <100000
, and when i test the input s, and use s to mod by prime.. if use all the primes < 100000, s still can't be 1, i wrote if (s>prime[10000]) digitsum(s)
and get RE

when i change the code to if (s!=1) the digitsum(s) directly... it's accept

thx your reply