본문 바로가기
Programming/Project Euler

515. Project Euler #515 : Dissonant Numbers

by 작은별하나 2015. 5. 13.

Original Problem : 


Let d(p,n,0) be the multiplicative inverse of n modulo prime p, defined as n × d(p,n,0) = 1 mod p.
Let  for k ≥ 1.

Let for all primes a ≤ p < a + b.


You are given:

  • D(101,1,10) = 45
  • D(103,102,102) = 8334
  • D(106,103,103) = 38162302

Find D(109,105,105).


This is "Number Theory" related problem. At this time, This problem is the most recent.  There are about 100 persons who solved it.


Consider mathematics respect;

1) It is hard to find inverse number of multiplcation at modula field.

2) If modula number p is a prime number, all modula numbers except 0 have their inverse of multiplcation.


For example, if p is a prime number 7, we can find their inverse of multiplcation.

1x1 = 1 (mod 7)

2x4 = 1 (mod 7)

3x5 = 1 (mod 7)

4x2 = 1 (mod 7)

5x3 = 1 (mod 7)

6x6 = 1 (mod 7)


For all prime numbers p, 1 and p-1 have self inverse number.


The most important thing is what is d(p, n, k).  In addition, final value of n is p-1.


The definition of d(p, n, k) is below;

d(p, n, k) is self calling function.  As decreasing k, there are very many function calls.  Obviously, If you make a program using above definition directrly, bigger p and k cannot be calculated within reasonable time.


First, I tried how many times d(p, i, 0) are called for calculating d(p, n, k) for 1 ≤ i ≤ p-1.  If present other form above equation;




Using above equation, define count array of d(p, i, 0) for 1 ≤ i ≤ p-1.


k = 1 :1 1 1 1 1 1 1 1 ...... 1

k = 2 :1 2 3 4 5 6 7 8 ...... n

k = 3 :1 3 6 10 15 21 28 36 ....... ??

...


We can find s'th element of k is made by sum of previous calculate number and itself.



For get count(k, i), we have to do k-1 add operations.  


My first base algorithm is;

1) pre-calculated count(k, i) for 1 ≤ i ≤ p-1.

2) For a prime number p,

3) foreach 1 ≤ i ≤ p-1

3-1) get inverse(i).

3-2) multiply count(k, i-1)

3-3) mod p

4) add the result to sum


Above Algorithm's oreder is very big. Calculating count(k, i) is O(pk).  If you use brute-force method for finding inverse of i, the order is O(p).  So overall order is O(pk+p^2b).  For get result, the order is 10's 23 power.


By the way, there are very big problems to use array size of p.

First, the counts of d(p, i, 0) are geometrically bigger as increase p.  If we use 64bit integers, we can store their value for even small p.  Using big integer can store the values, but its complexity is too big to run.

Second, the array size is too big to fit normal program.  Even if we use 64 bit integers, array size is 8 giga bytes to solve this problem.


So my first algorithm is useless.


To solve array problem, first I make direct equation for k and p.  Because combination have to be used, actually k order operations are needed.  This equation solve only array size problem.



In order to calculate this value faster, I use text search algorithm.  Refer this document.(http://odev.tistory.com/18)


Second algorithm problem is find inverse number of i at modula p field.

Brute force method will consume very big time because p's order is very big.


In order to find inverse number of i at modula p field, I used chinese remainder theorem.  The function to find inverse number lists below;


uint64_t findInverse(uint64_t p, uint64_t m)
{
    static int64_t rec[10000];
    uint64_t a = p;
    int count = 0;

    while( m ) { uint64_t t = m; rec[count++] = a/m; m = a%m; a = t; }
    int64_t s = 0, t = 1;
    count--;
    while( --count >= 0 )
    {
        int64_t r = t;
        t = -t*rec[count]+s;
        s = r;
    }
    t = (t>0)?t:p+t;
    return t;
}


Nevertheless all optimization algorithms are applied to my second algorithm, It's hard to solve this problem.  I guessed consuming time is 10,000 minutes which is about 1 week in my working computer.


I have the solution to solve this problem.  It is very simple, but hard to find.


I suggest these considerations.


1) To solve D(a, b, k), calculating d(p, n, k) mod p is needed. Not d(p, n, k).

2) What is Sum all d(p, i, 0) mod p.

3) It is trivial, needed i's range is not 1 to p-1.  Needed i's range is k-1 to p-1.

   How can reduce the range?








댓글