HDU-1576 A/B 基础数论+解题报告

题意

求(A/B)%9973，但由于A很大，我们只给出n(n=A%9973) (我们给定的A必能被B整除，且gcd(B,9973) = 1)。

输入

数据的第一行是一个T，表示有T组数据。
每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。

输出

对应每组数据输出(A/B)%9973。

解题思路

看到这里就能想到这个题是有关数论的了吧。

下面是对题目给的公式进行一些变形

设p=9973，令（C就是我们所要求的答案）

\[
\frac{A}{B}\ (mod\ p)=C
\]

\[
\frac{A}{B}=m*p+C
\]

\[
A=B*m*p+C*B
\]

因为
\[
A(mod\ p)=n
\]

所以对等式两边同时模p得

\[
n=C*B(mod\ p)
\]

显然这个\[C\]只需要在\[0-9973\]即可。

于是一个for循环来寻找满足这个条件的数就好了。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
typedef long long ll; //也可以不使用long long
using namespace std;

int main()
{
    ll t, n, b; 
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld%lld", &n, &b);
        for(ll i=0; i<=9973; i++)
        {
            if((b*i)%9973==n)
            {
                printf("%d\n", i);
                break;
            }
        }
    }
    return 0;
}

END

版权声明：本文为alking1001原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/alking1001/p/11228470.html