SPOJ MMOD29

Problem Link : http://www.spoj.pl/problems/MMOD29/en/

I was searching some problems that would require modular inverse / Chinese remainder theorem / Extended Euclidean algorithm. This problem requires the simplest case of modular inverse when the numbers in question are co-prime.

The problem in short

Find the sum of divisors of the number 2004^X mod 29 [1<=X<=10000000].

So, first we need to find the sum of divisors of an arbitrary number N. Let prime factorization of N is -

N = (p1^a1) * (p2^a2) * ...... * (pn^an)

Then the sum of its divisors would be -

S = (1 + p1 + ... +  p1^a1) * (1 + p2 + ... + p2^a2) * ...... * (1 + pn + ... + pn^an)

             = (p1^(a1+1) - 1) / (p1 - 1)  * (p2^(a2+1) - 1) / (p2 - 1) * ...... * (pn^(an+1) - 1) / (pn - 1)

You need to calculate S mod 29. The problem is all the terms in S are of the form (x/y). To calculate (x/y) mod m, we need to find a z such that -

(1/y) congruent to z (mod m)

If y and m are co-prime, then it is very easy to find. Modular inverse z would be

z = y ^ (phi(m) - 1) mod m

As m is a prime number in this problem, it will be co-prime with the prime factors of 2004 (which are 2,3 and 167) and phi(m) = m -1.

Combining all these equations, we can easily solve the problem.

Source code below -

/*
Problem Name : MMOD29
Problem Number : SPOJ 3909
Link : http://www.spoj.pl/problems/MMOD29/en/
Problem Type : Math
Difficulty : 4.5 / 10
Interest : 6 / 10
Complexity : O(lgX)
Date : December 2, 2010
*/

#include <stdio.h>

#define rep(i,n) for(i=0;i<(n);i++)

int bigmod(int b, int p, int m) {
 if(p == 0) return 1;
 if(p == 1) return b%m;
 if(p&1) return ((b%m) * bigmod(b,p-1,m)) % m;
 else {
  int sq = bigmod(b,p/2,m);
  return (sq * sq) % m;
 }
}

int main() {
 int n,res,i,x;
 int primes[] = {2,3,167};
 int powers[] = {2,1,1};
 int MOD = 29;
 while(scanf(" %d",&n) == 1) {
  if(n == 0) break;
  res = 1;
  rep(i,3) {
   x = (bigmod(primes[i],powers[i]*n+1,MOD) - 1 + MOD) % MOD;
   res = (res * x) % MOD;
   x = bigmod(primes[i]-1,MOD-2,MOD);
   res = (res * x) % MOD;
  }
  printf("%d\n",res);
 }
 return 0;
}