OJ Board

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;
}

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;
}

Code: Select all

3 2
0 0