c - Count distinct numbers constructed with k limited prime factors -

i can't understand solution following problem:

alice , bob playing game.

in game, players supposed show @ same time using hands integer between 0 , 10 million. if numbers shown both players equal, have tie. otherwise, players alternate writing down numbers in piece of paper.

let integer shown alice in beginning of match , let b integer show bob, each number written down must product of |a - b| factors, factors being prime numbers, not distinct, belonging interval defined integers , b.

alice play first.

for example, if = 2 , b = 5, there 10 numbers (bob wins) can written down in paper, are:

8 = 2 x 2 x 2    12 = 2 × 2 × 3   20 = 2 × 2 × 5   18 = 2 × 3 × 3   30 = 2 × 3 × 5   50 = 2 × 5 × 5   27 = 3 × 3 × 3   45 = 3 × 3 × 5   75 = 3 × 5 × 5   125 = 5 × 5 × 5   

the input has 2 numbers , b described.

the output has 1 line containing singly match winner's name, assuming both players play optimally. if match ties, output line shall contain singly symbol '?'.

here solution problem :

#include <stdio.h> #include <math.h> #include <string.h>  #define max 11234567  int primes[max], primeindex;  inline void sieve(int limit) {      bool sieve[limit];     memset(sieve, 0 , sizeof(sieve));      primeindex = 0;     primes[primeindex] = 2;      (int = 3; < limit ; += 2) {         if(!sieve[i]){             primes[++primeindex] = i;             (int j = + i; j <= limit; j += i) {                 sieve[j] = 1;             }         }     }      ++primeindex; }  inline int mul(int n) {     int ret = 0;     while (n > 0) {         n /= 2;         ret += n;     }     return ret; }  inline void swap(int *a, int *b){     int aux = *a;     *a = *b;     *b = aux; }  int main(void) {     int a, b;     scanf("%d %d", &a, &b);      if (a == b) {         puts("?");         return 0;     }      if (a > b) {         swap(&a, &b);     }       sieve(b);      int position_of_largest_prime;     (position_of_largest_prime = 0; position_of_largest_prime < primeindex && primes[position_of_largest_prime] < a; ++position_of_largest_prime);      int intervalba = b - a;     int primecount = (primeindex - position_of_largest_prime);      puts(primecount > 0 && mul(intervalba + primecount - 1) == mul(primecount - 1) + mul(intervalba) ? "alice" : "bob");      return 0; } 

mul(intervalba + primecount - 1) == mul(primecount - 1) + mul(intervalba)

i don't understand above condition. number theory problem ? can me identify ?

as pointed on answer there lack of information on description. here link problem detailed description.

there details game not explained. example, may case alice , bob not choose same number @ beginning of match, there no primes between chosen numbers. if = 14 , b = 16, tie? if so, not think solution provide correct in circumstances, since appears output bob rather ? in case primecount = 0. also, assuming whoever writes down last number winner, not stated in game description.

your primary question, though, seems combinatorics involved. if understand game correctly, if there prime numbers between , b, need determine whether number of distinct products of | b - | of these prime numbers or odd. first question 1 might ask is, "how many distinct products there?" 1 way count these use stars , bars approach. can read more stars , bars here, in example game, there |b-a| = 3 primes need chosen, i'll call 3 stars, , 2 bars, divider between prime 2 , 3 , divider between 3 , five. *|*|* represents product 2 x 3 x 5, **|*| represents product 2 x 2 x 3, , *||** represents product 2 x 5 x 5. notice number of bars 1 less number of primes in interval between , b inclusive. combinatorial problem, then, choosing locations of stars , bars within sequence whole. length of whole sequence intervalba + primecount - 1, , number of star locations choose intervalba.

if calculate number of different combinations there are, then, calculate how many combinations of size intervalba can made intervalba + primecount - 1 objects. in other words, compute intervalba + primecount - 1 choose intervalba. however, number exceed size of integer on computer working with, direct computation not feasible. instead should find way decide whether result of computation or odd without directly computing result.

deciding whether result or odd can done using lucas's theorem. i'll provide link wikipedia article theorem , question on math stack exchange 1 of comments discusses how lucas's theorem can applied answer question of whether combination or odd using binary representations of numbers.

the mul function of solution can used determine whether result or odd without directly computing result. different solution obtained lucas's theorem. it's not i've seen before, determined mul(n) computes largest power of 2 divide n factorial. using ! mean factorial, basic definition of n choose k given n!/(k!(n-k)!). condition mul(intervalba + primecount - 1) == mul(primecount - 1) + mul(intervalba) checking whether largest power of 2 divides numerator equal largest power of 2 divides denominator, n intervalba + primecount - 1 , k intervalba. if largest power of 2 divides numerator equal largest power of 2 divides denominator, n choose k odd number , alice win. otherwise n choose k , bob win.

code code in solution easier understand if documented does.