hdoj 5685 Problem A(逆元)

2019-04-14 18:51发布

站内文章 / 模拟电子
16753 0 1761
问题是求区间积。可以预处理前缀积h[i]（取模后），现在要求(h[b]/h[a-1])%mod，因为
这里的h[a-1]需要的是取模前的，所以不能直接用预处理的h[b]与h[a-1]相除， 此时需要
用到逆元( 逆元应用：(a/b)%mod = a*(b^-1)%mod )---->h[b]*(h[a-1]^-1)%mod.
这题求逆元的方法有很多，扩展gcd，费马小定理，线性求逆元。
方法一，扩展gcd： #include using namespace std; const int mod = 9973; const int maxn = 1e5+5; char str[maxn]; int h[maxn]; void ex_gcd(int a, int b, int &x, int &y) { if(!b) { x = 1, y = 0; return ; } ex_gcd(b, a%b, y, x); y -= (a/b)*x; } int main(void) { int q; h[0] = 1; while(cin >> q) { scanf(" %s", str); int len = strlen(str); for(int i = 0; i < len; i++) h[i+1] = h[i]*(str[i]-28)%mod; while(q--) { int a, b, x, y; scanf("%d%d", &a, &b); ex_gcd(h[a-1], mod, x, y); x = (x+mod)%mod; printf("%d ", h[b]*x%mod); } } return 0; }

方法二，费马小定理： #include using namespace std; const int mod = 9973; const int maxn = 1e5+5; char str[maxn]; int h[maxn]; int p(int a, int n) { int ans = 1; while(n) { if(n&1) ans = ans*a%mod; a = a*a%mod; n /= 2; } return ans; } int main(void) { int q, a, b; h[0] = 1; while(cin >> q) { scanf(" %s", str); int len = strlen(str); for(int i = 0; i < len; i++) h[i+1] = h[i]*(str[i]-28)%mod; while(q--) { scanf("%d%d", &a, &b); printf("%d ", h[b]*p(h[a-1], mod-2)%mod); } } return 0; }

方法三，线性筛选： #include using namespace std; const int mod = 9973; const int maxn = 1e5+5; char str[maxn]; int q, a, b, inv[maxn], h[maxn]; int main(void) { h[0] = inv[1] = 1; for(int i = 2; i < mod; i++) inv[i] = (mod-mod/i)*inv[mod%i]%mod; while(cin >> q) { scanf(" %s", str); int len = strlen(str); for(int i = 0; i < len; i++) h[i+1] = h[i]*(str[i]-28)%mod; while(q--) { scanf("%d%d", &a, &b); printf("%d ", h[b]*inv[h[a-1]]%mod); } } return 0; }



热门文章