I was trying to solve this problem uva 13136 Recurrences .

But, I couldn't manage to understand the output.

For example in test case 1, n = 1,A0 = 1,B0 = 2,C0 = 3. So, According to the relations given, I should get, S0 = 0
A1 = 4-6-9= -11
B1 = 5-8-12 = -15
C1 = 2-1 = 1 S1 = 0+(-11)*(-15)+1 = 166
so,ans should be 166%10 = 6. But the output is given 5.

LightOJ 1189 Sum of Factorail

Problem Statement : Given an integer n, you have to find whether it can be expressed as summation of factorials. For given n, you have to report a solution such that

n = x1! + x2! + ... + xn! (xi < xj for all i < j) Input

Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 1018). Output

For each case, print the case number and the solution in summation of factorial form. If there is no solution then print 'impossible'. There can be multiple solutions, any valid one will do. See the samples for exact formatting.

MEMORY LIMIT : 32 MB

My Code :

using namespace std;
ll fact[25];
map<ll,int>there;
bool Check_ON(int mask,int pos) //Check if pos th bit (from right) of mask is ON
{
    if( (mask & (1<<pos) ) == 0  )return false;
    return true;
}
void init()
{
    fact[0] = 1;
    loop(i,1,19)
    fact[i] = fact[i-1]*i;

    int maxMASK = (1<<20) - 1;

    loop(mask,0,maxMASK)
    {
        int curmask = mask;
        ll curN = 0;
        loop(bitpos,0,20-1)
        {
            if(Check_ON(curmask,bitpos))
            {
                curN+= fact[bitpos];
            }
        }
        there[curN] = mask;


    }

}
int main()
{
    init();
    //cout<<there.size()<<endl;
    int tc,cas  = 0;
    //write();
    sfi(tc);
    while(tc--)
    {
        map<ll,int>::iterator it;

        ll N;
        sfl(N);
        CASE(cas);

        it = there.find(N);
        if(it==there.end())
        {
            pf("impossible\n");
        }
        else
        {
            int mask = there[N];
            int flag = 0;
            loop(bitpos,0,20-1)
            {
                if(Check_ON(mask,bitpos))
                {
                    if(flag)
                        pf("+%d!",bitpos);
                    else
                        pf("%d!",bitpos);
                    flag = 1;
                }

            }
            pf("\n");


        }

        cout<<there.size()<<endl;




    }



    return 0;
}

The size of "there" is only 655360 . How did it consume 32 MB ?

I was trying to solve LightOJ 1278 this problem.

Problem statement : **Given an integer N, you have to find the number of ways you can

express N as sum of consecutive integers. You have to use at least two integers.

For example, N = 15 has three solutions, (1+2+3+4+5), (4+5+6), (7+8).**

Test cases : 200 , N <= 10^14

I came up with a O(sqrt(N)) solution like this , Try all possible lengths (length 2 to O(sqrt(N))) .

Code : —

int main()
{
    int tc,cas = 0;
    sfi(tc);
    while(tc--)
    {
        ll N;
        sfl(N);
        int up_b = (sqrt(8*N+1) - 1)/2;
        int ans = 0;
        loop(len,2,up_b)
        {
            if((len&1))
            {
                if(N%len==0)
                    ans++;

            }
            else
            {
                ll temp = N - len/2;
                if(temp!=0 && temp%len==0)
                    ans++;

            }
        }
        CASE(cas);
        pf("%d\n",ans);


    }



    return 0;
}

And I got TLE . I worked with some smaller N s and found out , that for all powers of 2 the answer is 0 , and for other numbers there 's a pattern with power , for example , ans[3] = 1, ans[9] = 2 , ans[27] = 3 . But , I couldn't find a way to exploit this. Need some hints to improve my run time .

Lets say I have a Big Integer A and an integer B . I want to calculate A mod B in O(number_of_digits_in(A)) complexity.

How can I do that?

This code snippet is from CP 3 by Steven Halim.This function takes 2 points on a circle and its radius and then calculates the center of the circle.Can someone explain the geometry behind?

bool circle2PtsRad(point p1, point p2, double r, point &c) {
  double d2 = (p1.x - p2.x) * (p1.x - p2.x) + 
              (p1.y - p2.y) * (p1.y - p2.y);
  double det = r * r / d2 - 0.25;
  if (det < 0.0) return false;
  double h = sqrt(det);
  c.x = (p1.x + p2.x) * 0.5 + (p1.y - p2.y) * h;
  c.y = (p1.y + p2.y) * 0.5 + (p2.x - p1.x) * h;
  return true; }