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

亦凉 2022-06-16 14:53 176阅读 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

发表评论取消回复

表情：

评论列表（有 0 条评论，176人围观）

还没有评论，来说两句吧...

相关阅读

相关费马大定理LA6862

![Center][] include<cstdio> include<iostream> using namespace std; int

系统管理员/ 2024年02月18日 14:08/ 0 赞/ 16 阅读

相关费马小定理【模板例题】

> 费马小定理： > 如果p是一个质数，而整数a不是p的倍数， > 则有a（p-1）≡1（mod p）。 > 即：假如a是整数，p是质数，且a,p互质(即两者只有一

蔚落/ 2022年12月10日 15:56/ 0 赞/ 199 阅读

相关欧拉函数和费马小定理（基础题题解）

太久没有在blog上记录学习进度啦，需要认真反思一下，陈老师的话如同醍醐灌顶，复习知识唤醒记忆，拥有一个属于自己的blog是一件引以为豪的事情，希望自己做的越来越好吧！加油！

Bertha 。/ 2022年09月29日 05:21/ 0 赞/ 179 阅读

相关费马小定理

费马小定理是 [数论][Link 1]中的一个重要定理，其内容为：假如p是 [质数][Link 2]，且(a,p)=1，那么 a^(p-1) ≡1（mod p

朱雀/ 2022年09月20日 15:29/ 0 赞/ 239 阅读

相关费马小定理与欧拉定理原理与证明

一、欧拉定理 1、定义若a与n互质，则 a φ ( n ) ≡ 1 a^\{\\varphi (n)\} \\equiv 1 aφ(n)≡1 (mod n)。

悠悠/ 2022年09月04日 15:53/ 0 赞/ 169 阅读

相关除法取模逆元费马小定理

对于正整数![20140613102654328][]和![20140613102712781][]，如果有![20140613102734984][]，那么把这个同余方程中!

忘是亡心i/ 2022年07月12日 11:49/ 0 赞/ 244 阅读

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

Think: 1快速幂 2费马小定理推论 [建议参考博客链接][Link 1] C~K的难题 Time Limit: 1000MS Memory Limit:

亦凉/ 2022年06月16日 14:53/ 0 赞/ 177 阅读

相关欧拉定理费马小定理

欧拉定理： > 若gcd(a,m)=1 g c d ( a , m ) = 1 ，则aφ(m)≡1(modm) a φ ( m ) ≡ 1 ( mod m ) 。其中

本是古典何须时尚/ 2022年06月02日 10:44/ 0 赞/ 195 阅读

相关费马小定理测素数

素性测试（Miller-Rabin测试）首先，一个叫费马的人提出：如果一个数p是质数，且gcd(a,p)==1。那么(a^p)%p==a，这就是费马小定理。然后我们反向利

拼搏现实的明天。/ 2022年03月20日 06:16/ 1 赞/ 281 阅读

相关 HDU - 4704 - Sum 【费马小定理 + 快速幂】题解

目录 1.题目 2.代码 1.题目 ![在这里插入图片描述][watermark_type_ZmFuZ3po

川长思鸟来/ 2021年07月24日 20:25/ 0 赞/ 340 阅读