Internet Problem Solving Contest

• Correct output – A1
• Correct output – A2

Let's go straight to the solutions. The easier one first.

#include <stdio.h>

int A[4000], B[4000];
int i,j,k,l,m;

int main(void) {
  for (i=0;i<4000;i++) { A[i]=B[i]=0; } k=-1; m=0;
  while (!A[1000]) {
    A[0]++; B[0]++;
    for (j=0;j<3999;j++) { B[j+1]+=B[j]/13; B[j]%=13; }
    for (j=0,l=-1;j<3999;j++) { 
      if ((A[j]>0) && (k<j)) { k=l=j; }
      A[j+1]+=A[j]/(j+2); A[j]%=(j+2); 
    }
    if (l>-1) m+=B[0];
  }
  printf("%d\n",m);
  return 0;
}

Initially, all elements in both arrays are set to 0. In each pass through the while cycle, we add 1 to both A[0] and B[0]. What happens with the array B? If B[0] is less than 13, nothing. If it is now equal to 13, we set B[0] to 0, increase B[1] and continue with B[1] in the same way. It is quite easy to find out, that after N passes through the cycle the numbers B[i] will be the digits of N in base 13. (The process done with this array corresponds to adding 1.) And what about array A? The element A[i] can only have values from 0 to i+1. If we look at this array in the same way, it makes us realize, that this process also corresponds to "adding 1" in some way. Exactly said, the sum A[0].(0+1)! + A[1].(1+1)! + ... + A[i].(i+1)! + ... + A[1000].(1000+1)! always increases by 1. The last question to answer: when is l>-1 (and the value of m altered)? It happens, when a non-zero element with the index greater than ever before occurs in the array A. This means, that it's the moment, when all elements of A but one are zero and that one element is 1. But this means, that if the index of the non-zero element is j, there were exactly (j+1)! passes through the cycle so far. And so B[0] (the last digit of (j+1)! in base 13) is (j+1)! mod 13.

It is already possible to solve this task by simply summing up all values of n! mod 13 for n from 1 to 1001, but we can make yet one simple observation. For n greater than 12, n! is divisible by 13. So it suffices to count the sum for n 1 to 12.

We have to apologize, because (despite our efforts) there was a small bug in the Pascal version of this problem -- the line writeln(m); at the end was missing. Some of you have notified us about this problem during the contest, but we decided that it is just a small bug that can easily be corrected by looking at the C version of this problem, and so we won't send you more than 500 emails with the correct input... We hope, that this small flaw didn't cause you any inconvenience.

---

And now the more difficult one:

#include <stdio.h>

int foo(int a, int b)
{
  return a<b?0:a-b;
}

int goo(int a, int b)
{
  return a+foo(b,a);
}

int boo(int a, int b)
{
  return a+b-goo(b,a);
}

int moo(int a, int b)
{
  int i,j,r;
  r = 0;
  for (i=b+boo(a,b)-goo(b,a); i<=b+foo(a,b)+foo(b,a)+7; i++) {
    if (i<=0) continue;
    j = foo(a%i, b%i) + foo(goo(a%i, 0), boo(b%i, 0));
    j += foo(b%i, a%i) + foo(boo(0, b%i), goo(0, a%i));
    if (!j) r=i;
  }
  return ( boo(r,b)==(a-foo(a,b)) );
}

int soo(int a)
{
  int i,s;
  s = 0;
  for (i=1; i<=goo(a,7)+boo(7,a)-7; i++)
    if (moo(a,i)) s++;
  return s;
}

int main(void){
  int i;
  i = 0;
  while(soo(i)!=7777)
    i++;
  printf("%d\n",i);
  return 0;
}

So, let's find out, what do the various functions do.

foo is fairly simple, it returns max(a-b,0). We may also note, that foo(a,b)+foo(b,a)=abs(a-b), it will be useful later.
if a>=b, goo returns a+max(b-a,0)=a+0=a.
if a<b, goo returns a+max(b-a,0)=a+(b-a)=b.
From these observations easily follows, that goo(a,b)=max(a,b)
And if goo(a,b)=max(a,b), then boo(a,b)=a+b-max(a,b)=min(a,b)

What about moo?
Let's take a look at the variable r. When does it change? Only if j is zero. So the value foo(a%i,b%i)+foo(b%i,a%i) + foo(goo(a%i,0),boo(b%i,0))+foo(goo(a%i,0),boo(b%i,0)) has to be zero.
First let's get rid of the goo and boo functions. It's trivial - goo(a%i,0)=a%i, boo(b%i,0)=0.
And from the properties of foo, we know, that this value is equal to abs(a%i - b%i) + abs(a%i - 0). This can happen only if a%i=b%i=0, so only if i divides both a and b. The value of i is then stored in r.
So at the end r contains the greatest i (from the interval we tried), that divides both a and b. Note that r can be at most b.
It is easy to note, that b+boo(a,b)-goo(a,b)<=b and that b+foo(a,b)+foo(b,a)+7&;gtb. So we always try the value b as i. When do we return true? Only if min(r,b)=r is equal to a-foo(a,b). As we will later see, each time this function is called, a>=b. And for such values of a and b is a-foo(a,b) equal to b. So our function moo returns true iff the greatest number dividing both a and b is b. In other words, it returns, whether b divides a. So simple ;-).

Well, the function moo does "all the hard work", the rest is again easy to understand. Function soo simply tries all values from 1 to a and returns, how many of them divide a. So it returns the number of divisors of a.

And in the main program we are looking for the smallest number with 7777 divisors. If we have the number N written as the product of different prime numbers N=p₁^a₁.p₂^a₂...p_k^a_k, each of its divisors can only contain the same prime numbers. And for the power of p_i in the divisor we have a_i+1 possibilities (0 to a_i). So this number has (a₁+1)(a₂+1)...(a_k+1) divisors.

7777=7.11.101, and from the observation above it is easy to find out, that the least number having this number of divisors is 2¹⁰⁰3¹⁰5⁶ This is quite a big number, so to compute its value, you had to write a simple program or to use some tool, which has implemented big numbers (e.g. bc under Linux, as I did...).