【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为偶数。

---

【题解】：

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

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 ll ex_gcd( ll a , ll b , ll &x , ll &y ){

     if( b ==  ){

         x =  ;

         y =  ;

         return a ;

     }

     ll r = ex_gcd( b , a%b , y , x );

     y -= x * ( a/b );

     return r ;

 }

 ll qpow( ll a , ll b , ll mod ){

     ll ans =  ;

     while( b ){

         if( b &  ){

             ans = ans * a % mod ;

         }

         a = a * a % mod ;

         b >>=  ;

     }

     return ans ;

 }

 ll Gcd , n , m , p , x , y , a , b ;

 int main()

 {

     ios_base :: sync_with_stdio(false);

     cin.tie(NULL) , cout.tie(NULL) ;

     cin >> n >> m >> p ;

     a = qpow(,m,n+) , b = n +  ;

     Gcd = ex_gcd( a , b , x , y );

     b /= Gcd , p /= Gcd ;

     x = ( x % b ) * p % b ;

     if( x <  ) x += b ;

     cout << x << endl ;

     return ;

 }