【exgcd】卡片

题目描述

你有一叠标号为1到n的卡片。
你有一种操作，可以重排列这些卡片，操作如下：
1.将卡片分为前半部分和后半部分。
2.依次从后半部分，前半部分中各取一张卡片，放到新的序列中。
例如，对卡片序列(1,2,3,4,5,6)操作后的结果为(4,1,5,2,6,3)。
现在你有一个初始为(1,2,3,⋯,n)的卡片序列，你需要求出进行m次操作之后第x个位置上的卡片的标号。

输入

第一行包含三个非负整数n,m,x。

输出

输出一行一个数，表示答案。

样例输入

6 2 3

样例输出

6

提示

对于60%的数据，m≤107。
对于100%的数据，0≤n,m,x≤109。
数据有梯度，保证n为偶数。

---

【题解】：

请移步到这里，卡片即可，我也是看了别人题解做的。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 ll ex_gcd( ll a , ll b , ll &x , ll &y ){
 5     if( b == 0 ){
 6         x = 1 ;
 7         y = 0 ;
 8         return a ;
 9     }
10     ll r = ex_gcd( b , a%b , y , x );
11     y -= x * ( a/b );
12     return r ;
13 }
14 ll qpow( ll a , ll b , ll mod ){
15     ll ans = 1 ;
16     while( b ){
17         if( b & 1 ){
18             ans = ans * a % mod ;
19         }
20         a = a * a % mod ;
21         b >>= 1 ;
22     }
23     return ans ;
24 }
25 ll Gcd , n , m , p , x , y , a , b ;
26 int main()
27 {
28     ios_base :: sync_with_stdio(false);
29     cin.tie(NULL) , cout.tie(NULL) ;
30     cin >> n >> m >> p ;
31     a = qpow(2,m,n+1) , b = n + 1 ;
32     Gcd = ex_gcd( a , b , x , y );
33
34     b /= Gcd , p /= Gcd ;
35     x = ( x % b ) * p % b ;
36
37     if( x < 0 ) x += b ;
38
39     cout << x << endl ;
40     return 0;
41 }