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?








저작자 표시 비영리 변경 금지
신고



This problem's solvers are under 100.  This is very hard problem, so I can't describe detail solving method in this blog.


This problem is.


Consider the Gaussian integer i-1. A base i-1 representation of a Gaussian integer a+bi is a finite sequence of digits dn-1dn-2...d1d0 such that:

  • a+bi = dn-1(i-1)n-1 + dn-2(i-1)n-2 + ... + d1(i-1) + d0
  • Each dk is in {0,1}
  • There are no leading zeroes, i.e. dn-1 ≠ 0, unless a+bi is itself 0

Here are base i-1 representations of a few Gaussian integers:

11+24i → 111010110001101
24-11i → 110010110011
8+0i → 111000000
-5+0i → 11001101
0+0i → 0

Remarkably, every Gaussian integer has a unique base i-1 representation!

Define f(a+bi) as the number of 1s in the unique base i-1 representation of a+bi. For example, f(11+24i) = 9 and f(24-11i) = 7.

Define B(L) as the sum of f(a+bi) for all integers ab such that |a| ≤ L and |b| ≤ L. For example, B(500) = 10795060.

Find B(1015) mod 1 000 000 007.


Shortly describing, If specified range's complex number convert to base i-1, how many digit 1 are appeard.


Gaussian prime number is the complex number which has integer parameters and cannot be devided by other Gaussian primes. Gaussian primes can be acquired by prime numbers.


i) prime numbers are Gaussian primes.  For example 3, 7, 11, 19, ...

ii) Other prime numbers will be complex number Gaussian primes.  Other primes are can be  for integers a and b.  Gaussian primes from prime number 2 are .  5 are .


I think that in order to solve this problem, above theory is not important.


This problem's order is very big, 10's 15 power.  If solve this problem with brute force method,  i-1 base conversions are needed.  


Conversion function GetGaussianInteger(r, i) can be listed as C++.

uint64_t GetGaussianInteger(int64_t r, int64_t i)
{
    uint64_t count = 0;

    while(r || i)
    {
        if( (r^i)&1 ) { r--; count++; }
        int64_t x = (i-r)/2;
        i = -(i+r)/2;
        r = x;
    }

    return count;
}

In order to is 1, rear part and imagenary part are (odd, even) or (even, odd).  Otherwise  wiill be 0.  If is 1, real part number decrease by one.  Then divide a+bi by i-1.  This function will be run till real part and imagenary part are all zero.


B(10000) can be get with brute force method, but If N is larger, the execution time is square order.  I think that brute force method order is .


My approach is reduce size by mathematical method.  If N is 10000, I reduce N to 5000.  My approach's order is .


To solve this problem, in my case, elapsed time is about 18ms.


Refer to this value.  If you want to know more values, add your comment, I'll reply.



저작자 표시 비영리 변경 금지
신고



This is a recent problem, so not now, difficulty rating is not determined.  I think difficulty rating is about 50%.


At my middle school hood, math teacher said that geometry problem can be solved if you draw lines properly.


This problem is sam.


This picture is that added lines and triangles on original problem image.





Make repairs to the line L in circle A, make repairs to the line L in circle B, doing circles in the center of the A side and the L-lining, we draw a line parallel to the L in the center of the circle C.


Then, as shown in Figure, three right triangles, A, B, and C are made by drawing lines.


The explanation of this issue from just the three of a right triangle. Since this course Pythagoras law to establish a right triangle. However, the base of the triangle A, B the base of the triangle, the basis on which the base of the triangle C, this can be thought of as a natural picture On no. Of course A, the sum of the base of B is equal to the length of it, you can see the base of C.


Be the first to reveal that it still displays the radius of each circle for each triangle.

Second, you should not be the judgment on the natural log base line.


If you properly apply mentioned above, even though you may be a little long to answer. I'd probably take longer if the order of a few minutes to several hours. Improving the speed can not be got only two of the above.


Project Euler sites be presented values ​​of S (100), can be difficult to determine the algorithm is correct.

Less the value of one on here.


S(100) = 3072

S(1000) = 311709

S(10000) = 31418891


저작자 표시 비영리 변경 금지
신고