“This is the first day of my participation in the Gwen Challenge in November. See details of the event: The last Gwen Challenge in 2021”.

Topic describes

Topic link

In recognition of their contribution to the exploration of Samuel Planet, they were invited to participate in the Samuel Planet Close-in manned expedition.

Because The planet Samuel is so far away that the scientists have to spend a considerable amount of time in the spacecraft, Xiao Ling suggests playing cards to kill the boredom of the long journey. After a few games, everyone decided that playing poker was too easy for such intelligent people. Someone proposed a new way of playing poker.

Is such definition for a shuffle of playing CARDS, will be a pile of N (N is an even number) CARDS, on average, is divided into two fold up and down, take a pile under the first as the first of a new stack, and then take a stack above the first as a new stack of a second, then take a pile under the second as a new stack of the third… This alternates until all cards are drawn.

If a pack of six cards 1, 2, 3, 4, 5, and 6 are shuffled, the process is shown in the figure below:You can see that after a shuffle, sequence 1, 2, 3, 4, 5, 6 becomes 4, 1, 5, 2, 6, 3. And, of course, if YOU shuffle the sequence again, you get 2, 4, 6, 1, 3, 5.

The game works like this: If you are given a deck of cards of length N, and the deck size increases continuously from 1 to N (regardless of suits), shuffle the deck M times. The scientist who was the first to say what the face size of the L card in the shuffled poker sequence was won. Little Lenovo wins the game, can you help him?

Input format

The input file contains three space-separated integers representing N, M, and L (0 < N≤10^10, 0 ≤M≤10^10, and N is even).

The output format

Prints the face size of a specified playing card in a single line.

Input and output examples

  • Enter the # 1
6 2 3
Copy the code
  • Output # 1
6
Copy the code
  • Instructions/Hints
0< N or less10^10 ，0M or less or less10^10And N is evenCopy the code

Front knowledge

Extended Euclidean algorithm

Bezu theorem

  • If there are integers a,b, and c, in the equation Ax +by=cax+by=cax+by=c, the unknowns x and y have integer solutions if and only if C is a multiple of GCD (a,b), where GCD (a,b) represents the greatest common factor of a and B.

Euclidean algorithm

  • gcd(a,b)=gcd(b,a%b)=… =gcd(d,0)=d

Algorithm template

int gcd(int a,int b){
	if(b==0) return a;
	else return gcd(b,a%b);
}
Copy the code

Extended Euclidean algorithm

  • Ax +by= GCD (a,b)ax+by= GCD (a,b).

Algorithm thought

According to the Euclidean algorithm an equation ax + by = GCD (a, b) = GCD (a, b) a % b = bx + (% b) y ‘=’… =1d+0y=gcd(a,b)ax+by=gcd(a,b)=gcd(b,a\%b)=bx’+(a\%b)y’=… = 1 d + 0, y = GCD (a, b) ax + by = GCD (a, b) = GCD (a, b) a % b = bx + (% b) y ‘=’… = 1 d + 0, y = GCD (a, b) Bx + (a % b) y ‘ ‘= bx’ + y (a – a/b ∗ b) ‘= ay’ + (x ‘- a/b ∗ y’) b = ax + bybx ‘+ (a \ % b) y = bx’ + (a – a/b * b) y ‘= ay’ + ‘- a/b * y (x) = ax + b bybx’ + (a % b) y ‘= bx’ + (a – A/b y ∗ b) ‘= ay’ + (x ‘- a/b ∗ y’) b = ax + by the x = x ‘, y = x ‘- a/b ∗ y = x’ x ‘, y = x ‘- a/b * y’ ‘x = x, y = x’ – a/b ∗ y ‘eventually The GCD (a, b) + 0 x0 y0 = GCD (a, b) the GCD (a, b) x_0 + 0 y_0 = GCD (a, b) the GCD (a, b) + 0 x0 y0 = GCD (a, b), namely x0 = 1, y0 ∈ Rx_0 = 1, y_0 \ in Rx0 = 1, y0 ∈ R, Obtained by x, yx, yx, y is just a set of special solution and general solution of (x + k ∗ b/d, y – k ∗ b/d) (x + k * b/d, y – k * b/d) (x + k ∗ b/d, y – k ∗ b/d), slightly derivation method

Algorithm template

typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y){
	if(b==0){
		x=1;//gcd(a,b)x=gcd(a,b)
		y=0;/ / y
		return a;
	}
	ll gcd=exged(b,a%b,x,y),r;
	r=x;
	x=y;//x=y'
	y=r-a/b*y;//y=x'-a/b*y'
	return gcd;
}
Copy the code

use

  1. Find the multiplicative inverse
  2. Solving ax + by + by = = cax cax + by = c
  3. Find the congruence equation

Multiplication identity: Any number multiplied by the identity is equal to this number, obviously the identity of multiplication is 1. Multiplicative inverse: Any number multiplied by its multiplicative inverse equals the identity element, such as 2*0.5=1, 0.5 is the multiplicative inverse of 1, but this is not what we need, we need the multiplicative inverse of integers under modular operations.

The binary fast power is multiplied by the binary turtle speed

Binary fast power

Binary power

  • Binary power is the common power operation simplification method, generally using recursive implementation, not recommended

Such as


a b = { a ∗ ( a 2 ) b 2 . b For an odd number ( a 2 ) b 2 . b For the even A ^ b = \ left \ {\ begin {array} {l} a * \ left (a ^ 2 / right) ^ {\ frac {b} {2}}, b \ text {for odd number} \ \ \ the left (a ^ 2 / right) ^{\frac{b}{2}},b\text{even}\\ end{array} \right.

This is going to be the recursive equation


f ( a . b ) = { 1 . b = 0 a ∗ f ( a 2 . b 2 ) . b For an odd number f ( a 2 . b 2 ) . b For the even F \ left (a, b \ right) = \ left \ {\ begin {array} {l} 1, b = 0 \ \ a \ * f left (a ^ 2, \ frac {b} {2} \ right), and b \ text {for odd number} \ \ f \ left ( A ^ 2, \ frac {b} {2} \ right), and b \ text {even} {array} \ \ \ \ end right.

Algorithm template

typedef long long ll;
ll efm(ll a,ll b,ll n){
	if(b==0) return 1;
	if(b&1) return a*efm(a*a%n,b>>1,n);
	else return efm(a*a%n,b>>1,n);
}
Copy the code

Fast power

  • The idea of binary is used to solve ABA ^ BAB quickly.

Algorithm thought

I’m going to use b for binary numbers, Such as 313 = 3 b1101 = 31 ∗ b1000 ∗ ∗ 31 b100 30 ∗ ∗ b10 ∗ ∗ 31 bl3 ^ 3 ^ {13} = {b1101} = 3 ^ 3 ^ b1000} {1 * * * b100 {1} * 3 ^ ^ 3 b10} {0 * * b1} {1 * 313 = 3 b1101 = 31 ∗ b1000 ∗ 31 ∗ b100 30 ∗ ∗ b10 ∗ ∗ b1 3 b10 = 31 (3 b1) 23 ^ {b10} = (3 ^ {b1}) 23 b10 = b1 (3) ^ 2 3 b100 = (3 b10) 23 ^ {b100} = (3 ^ {b10}) 23 b100 = (3 b10) ^ 2 3b1000=(3b100)23^{b1000}=(3^{b100})^23b1000=(3b100)2 The time complexity of this algorithm is O(log2b)O(log_2b)O(log2b).

Algorithm template

  • In general, the power of this algorithm is very large, and the result often needs to be modulo
typedef long long ll;
ll ksm(ll a,ll b,ll n){//a^b%n
	ll ret=1;// Multiply the result
	while(b>0) {// The non-zero power is calculated
		if(b&1) {// check whether the lowest value is 1,0 does not need to be multiplied
			ret=ret*a%n;
		}
		a=a*a%n;// From the above derivation we can get the square relation
		b>>=1;//b moves one bit to the right
	}
	return ret;
}
Copy the code

Two turtle speed times

  • Improvement of fast power algorithm

Problems existing in binary fast power algorithm

When using binary fast power multiplication, even though %n is used to prevent overflow, there is still an overflow because x*x%n is possible at x*x.

Binary multiplication

  • In fact, turtle speed multiplied by two versions, generally with recursive implementation, not recommended

Multiplication can be written as a sum, such as


3 ∗ 5 = 3 + 3 ∗ 4 = 3 + ( 2 ∗ 3 ) ∗ 2 = 3 + 6 ∗ 2 = 3 + 12 3 * 5 = 3 + 3 * 4 = 3 + (2 * 3) * 2 = 3 + 6 * 2 = 3 + 12

This is going to be the recursive equation


f ( a . b ) = { 0 . b = 0 a + f ( 2 a . b 2 ) . b For an odd number f ( 2 a . b 2 ) . b For the even F \ left (a, b \ right) = \ left \ {\ begin {array} {l} 0, a + b = 0 \ \ f \ left (2 a, \ frac {b} {2} \ right), and b \ text {for odd number} \ \ f \ left ( 2 a, \ frac {b} {2} \ right), and b \ text {even} {array} \ \ \ \ end right.

Algorithm template

typedef long long ll;
ll gsc(ll a,ll b,ll n){
	if(b==0) return 0;
	if(b&1) return (a+gsc((a<<1)%n,b>>1))%n;
	else return gsc((a<<1)%n,b>>1)%n;
}
Copy the code

Tortoise speed by

We can make x times y look like a fast power, Such as 3 5 = 3 ∗ ∗ b101 = 3 ∗ ∗ b1 (1 + 0 ∗ ∗ + 1 b10 b100) b101 = 3 * 3 * 5 = 3 * (1 + 1 * * b1 + 0 * b10 b100) 3 5 = 3 ∗ ∗ b101 = 3 ∗ ∗ b1 (1 + 0 ∗ ∗ + 1 b10 b100) B1 + 0 = 1 3 ∗ ∗ ∗ ∗ 3 b10 + 1 3 ∗ ∗ b100 = 1 b1 + 0 * 3 * 3 * * b10 b100 = 1 + 1 * 3 * 3 ∗ ∗ b1 + 0 ∗ ∗ 3 b10 + 1 3 ∗ ∗ b100 among them ∗b10=3∗b1+3 *b10 ∗b13*b10=3* B1 +3* B13 ∗b10=3∗ b10+3* B100 =3* b103*b100=3*b10+3* B10 ∗b10 Since this algorithm is even slower than the sum of for loops, it is named turtle speed multiplication and the time complexity is O(log2b)O(log_2b)O(log2b)

Algorithm template

typedef long long ll;
ll gsc(ll a,ll b,ll n){
	ll ret=0;// add the result
	while(b>0) {// Non-zero times is calculated
		if(b&1) {// Check whether the minimum value is 1. 0 does not need to be added
			ret=(ret+a)%n;
		}
		a=(a+a)%n;// From the above derivation we can get the square relation
		b>>=1;//b moves one bit to the right
	}
	return ret;
}
Copy the code

Fast power improvements

  • After introducing turtle speed multiplication, we can improve the fast power algorithm
typedef long long ll;
ll ksm(ll a,ll b,ll n){
	ll ret=1;
	while(b>0) {if(b&1){
			ret=gsc(ret,a,n);/ / modify
		}
		a=gsc(a,a,n);/ / modify
		b>>=1;
	}
	return ret;
}
Copy the code

Answer key

According to the title it is not difficult to see in NNN card XXX card after MMM lun shuffling and location LLL meet:


x ∗ 2 m = l ( m o d   n + 1 ) x*2^m=l(mod\ n+1)

There are two solutions:

  1. Solve the inverse element by congruence equation
  2. Let’s just solve the congruence equation

Because this paper aims to learn more knowledge, using inverse element solution method this is a linear congruence equation, requires fast power combination extended Euclidean algorithm to solve. Because the ax = b (mod n) ax = b (mod \ n) ax = b (mod n), d = GCD (a, n), t = n/dd = GCD (a, n), t = n/dd = GCD (a, n), t = n/d, X =(x%t+t)%tx=(x\%t+t)\%tx=(x \%t+t) %t in this case, aaa is even, n+1n+1n+1 is odd, then t=nt=nt=n

Fast power + turtle speed multiplication code

#include <iostream>
using namespace std;
typedef long long ll;
ll n,m,l,x,y;
ll gsc(ll x,ll m){
	ll ret=0;
	while(m){
		if(m&1) ret=(ret+x)%n;
		x=(x+x)%n;
		m>>=1;
	}
	return ret;
}
ll ksm(ll x,ll m){
	ll ret=1;
	while(m){
		if(m&1) ret=gsc(ret,x);
		x=gsc(x,x);
		m>>=1;
	}
	return ret;
}
ll exgcd(ll a,ll b,ll &x,ll &y){
	if(b==0){
		x=1;
		y=0;
		return a;
	}
	ll r=exgcd(b,a%b,x,y);
	ll c=x;
	x=y;
	y=c-a/b*y;
	return r;
}
int main(a){
	scanf("%lld%lld%lld",&n,&m,&l);
	n++;
	ll k=ksm(2,m);
	exgcd(k,n,x,y);
	x=gsc(l,x%n+n);
	printf("%lld",x%n);
	return 0;
}
Copy the code

Binary power + binary multiplication code

#include <iostream>
using namespace std;
typedef long long ll;
ll n,m,l,x,y;
ll efc(ll x,ll m){
	if(m==0) return 0;
	if(m&1) return (x+efc((x<<1)%n,m>>1))%n;
	else return efc((x<<1)%n,m>>1)%n;
}
ll efm(ll x,ll m){
	if(m==0) return 1;
	if(m&1) return efc(x,efm(efc(x,x)%n,m>>1));
	else return efm(efc(x,x)%n,m>>1);
}
ll exgcd(ll a,ll b,ll &x,ll &y){
	if(b==0){
		x=1;
		y=0;
		return a;
	}
	ll r=exgcd(b,a%b,x,y);
	ll c=x;
	x=y;
	y=c-a/b*y;
	return r;
}
int main(a){
	scanf("%lld%lld%lld",&n,&m,&l);
	n++;
	ll k=efm(2,m);
	exgcd(k,n,x,y);
	x=efc(l,x%n+n);
	printf("%lld",x%n);
	return 0;
}
Copy the code

extension

Quick take a

  • Cyan_rose introduced fast multiplication in the paper “On some methods and skills of low-level optimization of programs”

  • You can follow this code for fast multiplication
cin>>a>>b>>mod;
cout<<((a*b-(long long) ((long double)a*b/mod)*mod+mod)%mod);
Copy the code