HDU 5685 Problem A （求逆元）

http://acm.hdu.edu.cn/showproblem.php?pid=5685

(b/a) % mod = ( b*q ) % mod 。 其中 q 是 a 的逆元。

逆元模板：

int extendGcd(int a,int b,int &x,int &y)
{
    if (b==0)
    {
        x=1;
        y=0;
        return a;
    }
    int d= extendGcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

int mod_reverse(int b,int p)
{
    int x,y;
    int d = extendGcd(b,p,x,y);
    if(d==1) return (x%p + p)%p;
    else return -1;
}

本题代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MOD = 9973;
const int N = 1e5 + 100;
int Hash[N];
char s[N];
int extendGcd(int a,int b,int &x,int &y)
{
    if (b==0)
    {
        x=1;
        y=0;
        return a;
    }
    int d= extendGcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

int mod_reverse(int b,int p)
{
    int x,y;
    int d = extendGcd(b,p,x,y);
    if(d==1) return (x%p + p)%p;
    else return -1;
}

int main()
{
        int n;
        while(scanf("%d\n",&n)!=EOF)
        {
               gets(s+1); 
               Hash[0] = 1;
               for(int i=1;s[i];i++) Hash[i] = (Hash[i-1] * (s[i] - 28)) % MOD;
               while(n--)
               {
                       int l,r;
                       scanf("%d%d",&l,&r);
                       int p = mod_reverse(Hash[l-1],MOD);
                       int ans = (Hash[r] * p) % MOD;
                       printf("%d\n",ans);
               }
        }
        return 0;
}