hdu 1576

迈不过友情╰ 2023-02-27 10:59 34阅读 0赞

![博客图片][format_png]

## 题目链接 ##

[hdu1576][]

## 题目概述 ##

> 要求 ( A / B ) % 9973 (A/B)\\%9973 (A/B)%9973，但由于A很大，我们只给出 n ( n = A % 9973 ) n(n=A\\%9973) n(n=A%9973)(我们给定的A必能被B整除，且 gcd ⁡ ( B , 9973 ) = 1 \\gcd(B,9973) = 1 gcd(B,9973)=1).
> 
> 数据的第一行是一个 T T T，表示有 T T T组数据。  
> 每组数据有两个数 n ( 0 ≤ n < 9973 ) n(0 \\leq n < 9973) n(0≤n<9973)和 B ( 1 ≤ B ≤ 1 0 9 ) B(1 \\leq B \\leq 10^9) B(1≤B≤109).
> 
> 对应每组数据输出 ( A / B ) % 9973 (A/B)\\%9973 (A/B)%9973.

## 解题思路 ##

利用逆元算除法取模的概念题,当然求逆元也可以用费马小定理来做.

### 扩展欧几里得 ###

对于一个二元一次方程 a x + b y = n ,   a , b , n ∈ Z ax+by=n, \\, a,b,n\\in Z ax\+by=n,a,b,n∈Z当且仅当 gcd ⁡ ( a , b ) = n \\gcd(a,b)=n gcd(a,b)=n时方程有整数解.这个方程的解是先找到一个整数解 ( x 0 , y 0 ) (x\_0,y\_0) (x0,y0),然后通解:  
 \{ x = x 0 + b t y = y 0 − a t , t ∈ Z \\begin\{cases\} x = x\_0 + bt \\\\ y = y\_0 - at, \\qquad t \\in Z \\end\{cases\} \{ x=x0\+bty=y0−at,t∈Z  
把通解带入原来的方程得到:  
 a x + b y = a ( x 0 + b t ) + b ( y 0 − a t ) = a x 0 + b y 0 + ( a b t − b a t ) = n ( ∵ a x 0 + b y 0 = n ) \\begin\{aligned\} ax+by &= a(x\_0+bt)+b(y\_0-at)\\\\ &= ax\_0+by\_0 + (abt - bat)\\\\ &= n \\qquad(\\because ax\_0+by\_0=n) \\end\{aligned\} ax\+by=a(x0\+bt)\+b(y0−at)=ax0\+by0\+(abt−bat)=n(∵ax0\+by0=n)  
所以只要求出一个特解原方程的通解就可以求出.

扩展欧几里得对应的代码如下,可以求得方程 a x + b y = gcd ⁡ ( a , b ) ax+by=\\gcd(a,b) ax\+by=gcd(a,b)的一个特解 ( x 0 + y 0 ) (x\_0+y\_0) (x0\+y0).

void extend_gcd(ll a, ll b, ll & x, ll & y) {
        
        if( b == 0ll){
        
            x = 1;
            y = 0;
            return;
        }
        extend_gcd(b, a % b, x, y);
        ll temp = x;
        x = y;
        y = temp - (a / b) * y;
    }

### 逆元 ###

如果 a ( m o d m ) = b ( m o d m ) a \\pmod m = b \\pmod m a(modm)=b(modm),那么称 a , b a,b a,b模 n n n同余,记做 a ≡ b ( m o d m ) a \\equiv b\\pmod m a≡b(modm). a x ≡ b ( m o d m ) ax \\equiv b \\pmod m ax≡b(modm)成为一元线性同余方程,即 a x − b ax-b ax−b是 m m m的整数倍,从而 a x − b = m y ax-b=my ax−b=my,可以得到 a x + m y = b ax+my=b ax\+my=b,当 b = gcd ⁡ ( a , m ) b=\\gcd(a,m) b=gcd(a,m)时可以用扩展欧几里得来解.可以使用逆元来解上面方程的任意情形,设 a ′ a' a′是 a ( m o d m ) a \\pmod m a(modm)的逆元,即 a a ′ ≡ 1 ( m o d m ) aa'\\equiv1 \\pmod m aa′≡1(modm).将上面的等式同时乘以 a ′ a' a′,得到 a ′ a x ≡ a ′ b ( m o d m ) a'ax\\equiv a'b \\pmod m a′ax≡a′b(modm),即 x ≡ a ′ b ( m o d m ) x\\equiv a'b \\pmod m x≡a′b(modm).

对于方程 a x ≡ 1 ( m o d m ) , ax \\equiv1\\pmod m, ax≡1(modm),当 gcd ⁡ ( a , m ) = 1 \\gcd(a,m)=1 gcd(a,m)=1时,相当于解方程 a x + m y = 1. ax + my = 1. ax\+my=1.用前面的扩展欧几里得就可求出一个特解.

ll mod_inverse(ll a, ll m){
        
        ll x, y;
        extend_gcd(a, m, x, y);
        return ( m + x % m)% m;
    }

### 利用费马小定理求逆元 ###

> 若 p p p为素数, gcd ⁡ ( a , p ) = 1 \\gcd(a,p) = 1 gcd(a,p)=1,那么 a p − 1 ≡ 1 ( m o d p ) a^\{p-1\} \\equiv 1\\pmod p ap−1≡1(modp).  
> 另外一种形式:对于 a ∈ Z , a p ≡ a ( m o d p ) a\\in Z, a^p \\equiv a\\pmod p a∈Z,ap≡a(modp)

由上面的费马小定理可以推出方程 a x ≡ 1 ( m o d m ) , gcd ⁡ ( a , m ) = 1 ax \\equiv 1\\pmod m,\\gcd(a,m)=1 ax≡1(modm),gcd(a,m)=1的解 x = a m − 1 x = a^\{m-1\} x=am−1.利用快速幂取模可以进行计算.

ll fast_exp_mod(ll a, ll b, ll p){
        
        ll ans = 1;
        while( b ){
        
            if( b & 1){
        
                ans = (ans * a) % p;
            }
            b >>= 1;
            a = (a * a) % p;
        }
        return ans;
    }
    
    ll mod_inverse(ll a, ll m){
        
        return fast_exp_mod(a, m - 2, m) % m;
    }

## 代码实现 ##

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    
    
    const int M = 9973;
    
    ll fast_exp_mod(ll a, ll b, ll p){
        
        ll ans = 1;
        while( b ){
        
            if( b & 1){
        
                ans = (ans * a) % p;
            }
            b >>= 1;
            a = (a * a) % p;
        }
        return ans;
    }
    
    void extend_gcd(ll a, ll b, ll & x, ll & y) {
        
        if( b == 0ll){
        
            x = 1;
            y = 0;
            return;
        }
        extend_gcd(b, a % b, x, y);
        ll temp = x;
        x = y;
        y = temp - (a / b) * y;
    }
    
    ll mod_inverse(ll a, ll m){
        
        // ll x, y;
        // extend_gcd(a, m, x, y);
        // return ( m + x % m)% m;
        return fast_exp_mod(a, m - 2, m) % m;
    }
    
    int main(int argc, const char** argv) {
        
        int T;
        scanf("%d", &T);
        for (int i = 0; i < T; ++i){
        
            int n, b;
            scanf("%d%d", &n, &b);
            ll ans = mod_inverse(b, M);
            ans = (ans * n) % M;
            printf("%lld\n", ans);
        }
        return 0;
    }

## 其它 ##

[format_png]: /images/20230209/82cb9d7e2dbb4a8da22919b54711fd15.png
[hdu1576]: http://acm.hdu.edu.cn/showproblem.php?pid=1576