C~K的难题——费马小定理

亦凉 2022-06-16 14:53 142阅读 0赞

Think:  
1快速幂  
2费马小定理推论

[建议参考博客链接][Link 1]

C~K的难题  
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description  
众所周知 C~K 喜欢数学，但是他最近被一个题给难住了，题目是这样的。  
要求 (A/B)%10007，但由于 A 很大，我们只给出 n (n = A%10007)（我们给定的A必能被B整除，且 gcd(B,10007) = 1）。  
你能帮助他解答吗？他会很感谢你的。

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

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

Example Input  
2  
1000 53  
87 123456789

Example Output  
8893  
7424

Hint

Author  
「山东理工大学第一届ACM知识挑战赛（机试）」C~K

以下为Accepted代码

#include <bits/stdc++.h>
    
    using namespace std;
    
    long long power_mod(long long a, long long k, long long mod)///快速乘
    {
        long long ans = 1;
        while(k)
        {
            if(k & 1)///k是奇数
                ans = ans * a % mod;
            a = a * a % mod;
            k >>= 1;///k /= 2;
        }
        return ans;
    }
    
    const int mod = 10007;
    
    int main()
    {
        int T;
        long long n, b, x;
        scanf("%d", &T);
        while(T--)
        {
            scanf("%lld %lld", &n, &b);
            x = power_mod(b, mod-2, mod);
            printf("%lld\n", n * x % mod);///费马小定理
        }
        return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 0ms
    Take Memory: 192KB
    Submit time: 2017-05-17 17:30:48
    ****************************************************/

[Link 1]: http://blog.csdn.net/guhaiteng/article/details/52123385