欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Problem A

程序员文章站 2022-06-08 08:18:10
...

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5685

Problem A

Problem A

 分析: 此题本质是求Ar*A(r+1)*...An%p,亦即[(A1*A2*...An)/(A1*A2*...Ar-1)]%p,由于模运算的除法运算不能类比四则运算,即(a / b) % p (a % p / b % p) % p,我们需要用到乘法逆元,在此,先对乘法逆元有关的知识做些介绍。
  1. 对于正整数a和p,如果有a*k≡1 (mod p),那么同余方程中k的最小正整数解叫a模p的逆元
  2. 乘法逆元有如下定理:(a*k) mod p结果与(a/b) mod p等价,其中k为b关于p的乘法逆元(证明见后面的补充)
  3. 费马小定理:已知p是质数且gcd(a, p) = 1,则 ap-1 ≡ 1 (mod p),  所以 a*ap-2 ≡ 1 (mod p)

由以上三点知识,我们容易确定最终结果为h[b]*h[a-1]^(p-2) mod p,对于h[a-1]^(p-2),用快速幂或者扩展欧几里得算法来计算即可,时间效率为O(lgP)

#include <cstdio>
#include <iostream>
#include <cstring> 

using namespace std;
const int LEN = 100005;
const int P = 9973;

int N;
char s[LEN];
int h[LEN];

void PrePro(){
	int len = strlen(s);
	h[0] = 1;
	for(int i=1;i<=len;i++){
		h[i] = h[i-1]*(s[i-1]-28)%P;
	}
}

int KSM(int a, int n){//快速幂
	int ret = 1;
	int tmp = h[a-1];
	while(n){
		if(n&1) ret = ret*tmp%P;
		n >>= 1;
		tmp = tmp*tmp%P;
	}
	return ret;
}
void GetHashValue(){
	int a,b;
	for(int i=1;i<=N;i++){
		scanf("%d%d",&a,&b);
		//h[b]*h[a-1]^(P-2)modP
		printf("%d\n",h[b]*KSM(a,P-2)%P); 
	}
}

int main(){
	while(scanf("%d",&N)!=EOF){
		scanf("%s",s);
		PrePro();
		GetHashValue();
	}
	return 0;
}

乘法逆元定理的证明:

由b*k≡1 (mod p)有b*k=p*x+1,k=(p*x+1)/b,将k代入(a*k) mod p,得:

[a*(p*x+1)/b]mod p=[(a*p*x)/b+a/b]mod p(注意:只要a整除b,自然有(a*p*x)整除b)

={[(a*p*x)/b] mod p +(a/b)} mod p

={[p*(a*x)/b]mod p +(a/b)} mod p,而p*[(a*x)/b] mod p=0

=(a/b) mod p

参照: