中英网站模板,linux wordpress安装,做网站 卖会员,淄博网站建设公司乐达题意#xff1a;求(A/B)%9973#xff0c;但由于A很大#xff0c;我们只给出n(nA%9973)(我们给定的A必能被B整除#xff0c;且gcd(B,9973) 1)。
思维#xff1a;#xff08;1#xff09;逆元扩展欧几里得算法#xff1a;满足a*k≡1 (mod p)的k值就是a关于p的乘法逆元。…
题意求(A/B)%9973但由于A很大我们只给出n(nA%9973)(我们给定的A必能被B整除且gcd(B,9973) 1)。
思维1逆元扩展欧几里得算法满足a*k≡1 (mod p)的k值就是a关于p的乘法逆元。当且仅当gcd(k,p) 1,如果可逆则可定义除法 x/k x * a mod p
2扩展欧几里得算法递推公式:运用扩展欧几里德算法能解出gcd(a,b)a*x1b*y1的x1和y1的值。
3数学思维解法推等式枚举某数让等式成立。
4费马小定理
题目
要求(A/B)%9973但由于A很大我们只给出n(nA%9973)(我们给定的A必能被B整除且gcd(B,9973) 1)。
Input
数据的第一行是一个T表示有T组数据。 每组数据有两个数n(0 n 9973)和B(1 B 10^9)。
Output
对应每组数据输出(A/B)%9973。
Sample Input
2
1000 53
87 123456789
Sample Output
7922
6060
AC代码
逆元为什么要有乘法逆元呢 当我们要求a/b mod p的值且a很大无法直接求得a/b的值时我们就要用到乘法逆元。 我们可以通过求b关于p的乘法逆元k将a乘上k再模p即(a*k) mod p。其结果与(a/b) mod p等价。 (A/B)%9973但由于A很大且gcd(B,9973) 1)所以我们可以求B的逆元然后 k*B 1 mod n 然后改写式子 (A/B)%9973 A % 9973 * k%9973 B的逆元就用扩展欧几里德解 k*B 1 mod n -- k*B m*n 1;
#includeiostream/**逆元拓展欧几里得*/
#includecstdio
#includecmath
#includecstring
using namespace std;
typedef long long int64;
int64 Exgcd(int64 a,int64 b,int64 x,int64 y)
{if(b 0){x 1,y 0;return a;}else{int64 r Exgcd(b,a%b,x,y);int64 temp x;x y, y temp - a/b*y;return r;}
}
int main()
{int t;int64 n,b 9973,B,x,y;scanf(%d,t);while(t--){scanf(%I64d%I64d,n,B);int64 d Exgcd(B,b,x,y);b b / d;x x / d ;x (x % b b) % b;/*求a最小正整数逆元xx0(a/gcd)*t*/printf(%I64d\n,(n%9973 * x%9973)%9973);/*x为n的逆元*/}return 0;
}拓展欧几里得
根据题目我们知道 nA%9973则nA-A/9973*9973。又A/Bx则ABx。所以Bx-A/9973*9973n。即Bx-9973yn。 在这里我们知道只要求出x的值就能算出x%9973的值也就是(A/B)%9973的值。 利用扩展欧几里德算法可求出gcd(B,9973)Bx19973y11的x1。题中说gcd(B,9973)1所以等式两边 同乘以n得B(n*x1)-9973(-n*y1)n。可知n*x1就是B*x-9973*yn的解了即xn*x1。 在扩展欧几里得算法中得到的x可能为负值所以还需要x(x%99739973)%9973。
#includecstdio/**推等式拓展欧几里得*/
#includecstring
void extgcd(int a,int b,int x,int y)
{if(b0){x1;y0;return ;}else{extgcd(b,a%b,y,x);y-(a/b)*x;}
}int main()
{int t,n,b,x,y;scanf(%d,t);while(t--){scanf(%d%d,n,b);extgcd(b,9973,x,y);x*n;x(x%99739973)%9973;printf(%d\n,x);}return 0;
} 数学思维解法
思路设XA/B%9973 因为nA%9973所以Ak*9973n (k为一常数) 又因为XA/B%9973所以A/Bd*9973X d为一常数 两边同乘以B得AB*d*9973B*X 即B*d*9973B*Xk*9973n 移项得 B*d*9973B*X-nk*9973 所以题意转为 只要满足B*X-n%99730X即为要求的结果。n的值知道B的值知道又因为x的取 值范围是0到9972因此枚举x的值即可满足条件的就是答案。
#includecstdio/**推等式枚举某数让等式成立*/
int main()
{int n,a,i,t;long long b;scanf(%d,t);while(t--){scanf(%d%lld,n,b);for(i0;i9973;i){if((b*i-n)%99730)break;}printf(%d\n,i);}return 0;
}4费马小定理易知费马定理是有限制的a与p要互质 #includeiostream
#includestring.h
#includealgorithm
using namespace std;
typedef long long ll;
int t;
ll n,m;
const int mod9973;
int quickpow(ll a,ll b){ll ans1;a%mod;while(b){if(b1) ansans*a%mod;b1;aa*a%mod;}return ans;
}
int main(){cint;while(t--){cinnm;//cout******endl;coutn*quickpow(m,mod-2)%modendl;}return 0;
}
//费马小定理
