11083 - Zeroes Revisited

[Ashkankhan]

is there any idea about this problem?

[Martin Macko]

is there any idea about this problem?

First, think what is the statement that b is always a square free number good for. Afterwards... find the formula

[Ashkankhan]

Dear martin can u solve this test case : 10 14?

[CodeMaker]

7 is the greatest prime factor of base 14 , so whenever a 7 is introduced, an extra zero will be added

so from 0! to 6! there is no 7 and so, we dont have any trailing zero, then from 7! to 13! each has 1 seven so, we have a trailing zero for each of them,

so , for 7,8,9 and 10 we have 1 trailing zero for each. and thus the answer will be 4.

[Ashkankhan]

tnx CodeMaker.

[temper_3243]

Algorithm is as follows
1) Until base limit(base = 10^5) find the highest prime that divides each number.
Now that is p for the formula.

Then the forumula for number of zeroes is
where i =p,p^2,p^3 and zee = (1 + 2 + ... k-1) , where k = a/p;

sum += zee * i + (a - (k * i) + 1) * k;

Did i make any mistakes here.


I am getting WA . Can somone post some test cases where my code fails for the accepted solution.

Code: Select all

#include<stdio.h>
#include<math.h>
#define MAX 100001
int arr[MAX];

void
genprimes (void)
{
  int i, j;

  arr[1] = arr[0] = 1;

  for (i = 4; i < MAX; i += 2)
    arr[i] = 2;


  for (i = 3; i < 400; i += 2)
    {

      if (arr[i] != 0)
	continue;


      for (j = i; i * j < MAX; j += 2)
	arr[i * j] = j;
    }

  return;
}

unsigned long long
z (unsigned long long num, int b)
{
  unsigned long long sum = 0, i;
  for (i = b; i <= num; i *= b)
    sum += num / i;

  return sum;
}



int
main ()
{
  int b, no, tmp, max, store, j;
  unsigned long long a, sum = 0, i, k, zee;

  genprimes ();

  for (j = 3; j < MAX; j += 2)
    {
      tmp = j;
      max = -1;
      if (arr[j] == 0)
	continue;


      while (arr[tmp] != 0)
	{
	  store = tmp / arr[tmp];
	  if (store > max)
	    max = store;
	  tmp = arr[tmp];
	}
      if (tmp > max)
	max = tmp;
      arr[j] = max;
    }

  arr[2] = 2;
  for (j = 4; j < MAX; j += 2)
    {
      if (arr[j / 2] == 0)
	arr[j] = j / 2;
      else
	arr[j] = arr[j / 2];
    }

  for (j = 3; j < MAX; j += 2)
    if (arr[j] == 0)
      arr[j] = j;

  while (scanf (" %llu %d", &a, &b) != EOF)
    {
      if (a == 0 && b == 0)
	break;

      if (a == 0 || a == 1)
	{
	  printf ("0\n");
	  continue;
	}
      no = arr[b];
      sum = 0;
      sum = 0;

/*

//	Check manually 

      for (i = 0; i * no <= a; i++)
	{
	  if ((i + 1) * no <= a)
	    k = no * z (i * no, no);
	  else
	    k = (no - ((i + 1) * no - a) + 1) * z (i * no, no);

//        printf ("%llu\n", k);
	  sum += k;
	}



      printf ("%llu\n", sum);
*/
      sum = 0;

      for (i = no; i <= a; i *= no)
	{
	  k = a / i;
	  if (k >= 1)
	    {
	      zee = 1;
	      if (k % 2==0)
		{
		  zee = k / 2;
		  zee *= k - 1;
		}
	      else
		{
		  zee = 1;
		  zee = (k - 1) / 2;
		  zee *= k;
		}
	      sum += zee * i + (a - (k * i) + 1) * k;
	    }
	  else
	    {
	      sum += 0;
	    }
	}
      printf ("%llu\n", sum);

    }
  return 0;
}

[temper_3243]

can someone post test cases please

[ayon]

try the inputs:
0 2
1 2
4000000000 2
4000000000 81510
0 0

output from my ac program:
0
0
7999999938612287475
444444430281766415

by the way it's not necessary to generate the primes, my program runs in 0.008 sec and it is only 5-6 line.

[temper_3243]

81510 is not a square free number (divisible by 13^2).

4900377 2006-09-03 21:50:41 Accepted 0.027 Minimum terry M C++ 11083 - Zeroes Revisited

My email address is niklaus@gmail.com.

All the accepted users , if you don't store anything can you tell me how you are doing
Can you please send me your 5 -6 line code. I just want to see it how could you do it and what is formula. Can you give me the link or the formula how you derived.

[mf]

81510 is not a square free number (divisible by 13^2).

Really?
81510=2*3*5*11*13*19

[temper_3243]

oh ! sorry my mistake , i thought 143 =13 *13 (which is wrong ) 143=13*11.

[ayon]

first loop O(sqrt(b)) to get the maximum prime factor p of b,
second loop to run the formula in O(logn/logp) time
thats all i did

temper_3243: i sent my code

[navid_a2b]

My program gives the correct output to sample and all test data in board ,
but I'm still getting WA , can anyone help me , here is my code :

Code: Select all

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

#define maxBase 100001
int maxPrimeFactor[maxBase] ;

int main()
{
	maxPrimeFactor[0] = maxPrimeFactor[1] = 0 ;
	for( int i=2 ; i<maxBase ; i++ ) maxPrimeFactor[i] = 1 ;
	for( int i=2 ; i<maxBase ; i++ )
	{ if( maxPrimeFactor[i]==1 ){for( int j=i ; j<maxBase ; j+=i ) maxPrimeFactor[j] = i ; }}

	unsigned long long n , ans , temp ; 
	unsigned long long b , p , k , q ;
	while( cin >> n >> b )
	{
		if( n==0 && b==0 )
			break ;
		ans = 0 ;
		p = maxPrimeFactor[b] ;
		q = p ;
		while(true)
		{
            k = n / q ;
			if( k==0 )
				break ;
			ans += q * ( k*(k-1)/2 ) ;
			ans += ( (n+1)%q ) * k ;
			q *= p ;
		}
		cout << ans << endl ;
	}
	return 0;
}

[Robert Gerbicz]

My program gives the correct output to sample and all test data in board ,
but I'm still getting WA , can anyone help me , here is my code :

I think your program gives wrong answer for:

Code: Select all

3 2
0 0