首页 > 代码库 > A/B
A/B
A/B
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5539 Accepted Submission(s): 4320
Problem Description
要求(A/B)%9973，但由于A很大，我们只给出n(n=A%9973)(我们给定的A必能被B整除，且gcd(B,9973) = 1)。
Input
数据的第一行是一个T，表示有T组数据。
每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。
每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。
Output
对应每组数据输出(A/B)%9973。
Sample Input
2
1000 53
87 123456789
Sample Output
7922
6060
就是问你会不会费马小定理求模的逆元，A/B 的模不能直接除了就取余，要当做 (A* (1/B) ）%m 所以就是求 1/B
费马小定理: 当m为质数的时候 A^(m-1) = 1 (mod m) 即 A^(m-2) = 1/A (mod m) 两边都余 m
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 5 using namespace std; 6 7 #define MOD 9973 8 9 int main()10 {11 int T;12 cin>>T;13 while(T--)14 {15 int a,b;16 scanf("%d%d",&a,&b);17 b%=MOD;18 int c = b;19 for (int i=0;i<MOD-3;i++)20 c = (c*b)%MOD;21 a = (a*c)%MOD;22 printf("%d\n",a);23 }24 return 0;25 }
A/B
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。