（待定系数法）A/B

　

待定系数法

题目：

要求(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)。

Output

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

Sample Input

2

1000 53

87 123456789

Sample Output

7922

6060

分析与解答：

参考：https://blog.csdn.net/triple_wdf/article/details/50979667

设X=(A/B)%9973 ==> A/B=k*9973+X (k为正整数) ==> A=k*9973*B+X*B

又因为n=A%9973 ==> A=p*9973+n (p为正整数) ==> p*9973+n=k*9973*B+X*B ==> p*9973-k*9973*B=X*B-n 从这个式子可以看出左半边可以被9973整除，所有可得(X*B-n)%9973=0;

这种题给我了一个思路，

1.如果是求某个数的余数，那么可以利用枚举求

2.如果是求一个数，可以先把他设出来，这样就形成了一个等式

3.n=A%9973可以转化为另一种表达形式，A=n+k*9973，这个表达式好在他的符号就只是属于四则运算，方便化简，以后遇见%，就把他去掉

4.找等式两边的关系，比如一边是某个数的倍数，那么另一边也一定是那个数的倍数。如果另一边只有一个变量，那就可以枚举求出来

代码：

#include<iOStream>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--)
    {
        long long n,b;
        cin>>n>>b;
        for(int i=1;i<9973;++i){
            long long sum=(i*b-n)%9973;
            if(sum==0){
                cout<<i<<endl;
                break;  
            }
        }
    }
}

相关阅读